ZJ Day10

数学高手：

可以发现这个数列会先在一定幅度内上下波动，随后不断减小或增大，而波动段的长度不会超过log,因为最坏情况为k=1，参考斐波那契数列。因此只需要暴力计算前部波动部分随后根据单调性取最大或最小值。

墅居结垢：

考虑维护不在集合中的最小非负整数，使用单调队列维护，从小到大，每次插入时从尾部删除，因为发现被删除的部分肯定早于当前插入的数字被插入原集合，不会对答案产生影响。

[NOI2005] 维护数列：

平衡树的进阶板题，使用与线段树类似的思路维护，注意旋转的懒标记下传时操作的顺序即可。
code:

#include<bits/stdc++.h>
//#define int long long
#define N 4000010
using namespace std;
int n,m;

int tot,rt,ls[N],rs[N],pri[N],siz[N];

int tag[N],sum[N],num[N];

int lmn[N],rmn[N],mmn[N];

bool rev[N];

mt19937 rng(time(0));

void pushup(int q)
{
    sum[q]=sum[ls[q]]+sum[rs[q]]+num[q];
    siz[q]=siz[ls[q]]+siz[rs[q]]+1;

    lmn[q]=max(max(lmn[ls[q]],sum[ls[q]]+num[q]),sum[ls[q]]+num[q]+lmn[rs[q]]);
    rmn[q]=max(max(rmn[rs[q]],sum[rs[q]]+num[q]),sum[rs[q]]+num[q]+rmn[ls[q]]);
    mmn[q]=max(max(num[q],rmn[ls[q]]+num[q]+lmn[rs[q]]),max(rmn[ls[q]]+num[q],num[q]+lmn[rs[q]]));

    return;
}
void modify(int q,int val)
{
    tag[q]=val;
    sum[q]=val*siz[q];
    num[q]=val;
    if(val>0)
    {
        lmn[q]=val*siz[q];
        rmn[q]=val*siz[q];
        mmn[q]=val*siz[q];
    }
    else
    {
        lmn[q]=val;
        rmn[q]=val;
        mmn[q]=val;
    }
    return;
}
void reverse(int q)
{
    rev[q]^=1;
    swap(ls[q],rs[q]);
    swap(lmn[q],rmn[q]);
    return;
}
void pushdown(int q)
{
    if(tag[q])
    {
        modify(ls[q],tag[q]);
        modify(rs[q],tag[q]);
        tag[q]=0;
    }
    if(rev[q])
    {
        reverse(ls[q]);
        reverse(rs[q]);
        rev[q]=false;
    }
    return;
}
int merge(int l,int r) //l<=r
{
    if(l==0||r==0) 
    {
        return l+r;
    }
    if(pri[l]>pri[r]) 
    {
        pushdown(l);
        rs[l]=merge(rs[l],r);
        pushup(l);
        return l;
    }
    else
    {
        pushdown(r);
        ls[r]=merge(l,ls[r]);
        pushup(r);
        return r;
    }
}
void split(int q,int k,int &l,int &r)
{
    if(q==0)
    {
        l=r=0;
        return;
    }
    pushdown(q);
    if(siz[ls[q]]+1<=k)
    {
        l=q;
        split(rs[q],k-siz[ls[q]]-1,rs[q],r);
    }
    else
    {
        r=q;
        split(ls[q],k,l,ls[q]);
    }
    pushup(q);
    return;
}
int newnode(int val)
{
    tot++;
    pri[tot]=rng();
    lmn[tot]=rmn[tot]=mmn[tot]=val;
    sum[tot]=num[tot]=val;
    siz[tot]=1;
    return tot;
}

void INSERT()
{
    int pos,cnt,x,a,b;
    cin>>pos>>cnt;
    split(rt,pos,a,b);
    for(int i=1;i<=cnt;i++)
    {
        cin>>x;
        a=merge(a,newnode(x));
    }
    rt=merge(a,b);
    return;
}
void DELETE()
{
    int pos,cnt,a,b,c;
    cin>>pos>>cnt;
    split(rt,pos-1,a,b);
    split(b,cnt,b,c);
    rt=merge(a,c);
    return;
}
void MAKE_SAME()
{
    int pos,cnt,x,a,b,c;
    cin>>pos>>cnt>>x;
    split(rt,pos-1,a,b);
    split(b,cnt,b,c);
    modify(b,x);
    rt=merge(merge(a,b),c);
    return;
}
void REVERSE()
{
    int pos,cnt,a,b,c;
    cin>>pos>>cnt;
    split(rt,pos-1,a,b);
    split(b,cnt,b,c);
    reverse(b);
    rt=merge(merge(a,b),c);
    return;
}
void GET_SUM()
{
    int pos,cnt,a,b,c;
    cin>>pos>>cnt;
    split(rt,pos-1,a,b);
    split(b,cnt,b,c);
//  debug(b);
    cout<<sum[b]<<endl;
    rt=merge(merge(a,b),c);
    return;
} 
void MAX_SUM()
{
    cout<<max(mmn[rt],max(lmn[rt],rmn[rt]))<<endl;
    return;
}
int main()
{
    freopen("P2042_2.in","r",stdin);
    freopen("aha.out","w",stdout);
    cin>>n>>m;
    int t;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        rt=merge(rt,newnode(t));
    }
    char op[10];
    while(m--)
    {
        cin>>op;
        if(op[0]==&#039;I&#039;) 
        {
            INSERT();
        }
        else if(op[0]==&#039;D&#039;)
        {
            DELETE();
        }
        else if(op[0]==&#039;M&#039;&&op[2]==&#039;K&#039;)
        {
            MAKE_SAME();
        }
        else if(op[0]==&#039;R&#039;)
        {
            REVERSE();
        }
        else if(op[0]==&#039;G&#039;)
        {
            GET_SUM();
        }
        else
        {
            MAX_SUM();
        }
    }
    return 0;
}