Luogu | P2042 [NOI 2005] 维护数列 | 数据结构 | 平衡树


Description

请写一个程序,要求维护一个数列,支持以下 $6$ 种操作:(请注意,格式栏中的下划线_表示实际输入文件中的空格)

2042


Input Format

输入文件的第 $1$ 行包含两个数 $N$ 和 $M$,$N$ 表示初始时数列中数的个数,$M$ 表示要进行的操作数目。

第 $2$ 行包含 $N$ 个数字,描述初始时的数列。 以下 $M$ 行,每行一条命令,格式参见问题描述中的表格。


Output Format

对于输入数据中的 GET-SUMMAX-SUM 操作,向输出文件依次打印结果,每个答案(数字)占一行。


Input Sample

Sample 01

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM


Output Sample

Sample 01

-1
10
1
10


Data Range

$1 \le M \le 2\times 10^5$。

任何时候数列中最多含有 $5\times 10^5$ 个数。

数列中插入数字总数不超过 $4 \times 10^6$。

数列中任何一个数字均在 $[-10^3,10^3]$ 以内。


Solution

Splay 维护数列。

考虑用 $lsum[x]$ 维护以 x 为根的子树代表的区间中包含区间左端点的最大前缀和,$rsum[x]$ 维护以 x 为根的子树代表的区间中包含区间右端点的最大后缀和,$msum[x]$ 维护区间最大子段和。

需要注意两点:

  • 最大子段和至少包含一个元素。
  • 垃圾回收。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define Rel(x) ch[fa[x]][1]==x
#define Link(x,y,z) fa[x]=y,ch[y][z]=x

using std::max;
using std::swap;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int M;
int top;
int root;

int fa[500010];
int seq[500010];
int val[500010];
int sum[500010];
int size[500010];

int lsum[500010];
int rsum[500010];
int msum[500010];

int r_tag[500010];
int m_tag[500010];

int stk[500010];

int ch[500010][2];

char inst[15];

void Maintain(int x){
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
    lsum[x]=max(lsum[ch[x][0]],sum[ch[x][0]]+val[x]+lsum[ch[x][1]]);
    rsum[x]=max(rsum[ch[x][1]],sum[ch[x][1]]+val[x]+rsum[ch[x][0]]);
    msum[x]=max(rsum[ch[x][0]]+val[x]+lsum[ch[x][1]],max(msum[ch[x][0]],msum[ch[x][1]]));
    return;
}

void Adjust(int x){
    if(m_tag[x]){
        rep(i,0,1){
            m_tag[ch[x][i]]=1;
            val[ch[x][i]]=val[x];
            sum[ch[x][i]]=val[x]*size[ch[x][i]];
            if(val[x]>0)
                lsum[ch[x][i]]=rsum[ch[x][i]]=msum[ch[x][i]]=sum[ch[x][i]];
            else
                lsum[ch[x][i]]=rsum[ch[x][i]]=0,msum[ch[x][i]]=val[ch[x][i]];
        }
        r_tag[x]=0;
        m_tag[x]=0;
    }
    if(r_tag[x]){
        int y;
        rep(i,0,1){
            y=ch[x][i];
            r_tag[y]^=1;
            swap(lsum[y],rsum[y]);
            swap(ch[y][0],ch[y][1]);
        }
        r_tag[x]=0;
    }
    return;
}

void Rotate(int x){
    int y=fa[x];
    int z=fa[y];
    bool d=Rel(x);
    Link(x,z,Rel(y));
    Link(ch[x][!d],y,d);
    Link(y,x,!d);
    Maintain(y);
    Maintain(x);
    return;
}

void Splay(int x,int dest){
    int y,z;
    while(fa[x]!=dest){
        y=fa[x],z=fa[y];
        if(z!=dest)
            Rel(x)^Rel(y)?Rotate(x):Rotate(y);
        Rotate(x);
    }
    if(!dest)
        root=x;
    return;
}

int Kth(int k){
    int u=root;
    if(size[u]<k)
        return -1;
    while(1){
        Adjust(u);
        if(size[ch[u][0]]>=k)
            u=ch[u][0];
        else if(size[ch[u][0]]+1>=k)
            return u;
        else{
            k-=size[ch[u][0]]+1;
            u=ch[u][1];
        }
    }
    return -1;
}

int Build(int L,int R){
    if(L>R)
        return 0;
    int now=stk[top--];
    int mid=(L+R)>>1;
    size[now]=1;
    val[now]=seq[mid];
    if(seq[mid]>0)
        lsum[now]=rsum[now]=msum[now]=sum[now]=seq[mid];
    else
        lsum[now]=rsum[now]=0,msum[now]=sum[now]=seq[mid];
    if(L==R) return now;
    ch[now][0]=Build(L,mid-1);
    ch[now][1]=Build(mid+1,R);
    if(ch[now][0])
        fa[ch[now][0]]=now;
    if(ch[now][1])
        fa[ch[now][1]]=now;
    Maintain(now);
    return now;
}

void Empty(int x){
    fa[x]=0;
    val[x]=0;
    sum[x]=0;
    size[x]=0;
    ch[x][0]=ch[x][1]=0;
    m_tag[x]=r_tag[x]=0;
    lsum[x]=rsum[x]=msum[x]=0;
    stk[++top]=x;
    return;
}

void Travel(int x){
    if(ch[x][0])
        Travel(ch[x][0]);
    if(ch[x][1])
        Travel(ch[x][1]);
    Empty(x);
    return;
}

void Delete(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    Travel(ch[tl][0]);
    ch[tl][0]=0;
    Maintain(tl);
    Maintain(hd);
    return;
}

void Modify(int s,int k,int v){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    val[x]=v;
    m_tag[x]=1;
    sum[x]=size[x]*v;
    if(v>0)
        lsum[x]=rsum[x]=msum[x]=sum[x];
    else
        lsum[x]=rsum[x]=0,msum[x]=v;
    Maintain(tl);
    Maintain(hd);
    return;
}

void Reverse(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    r_tag[x]=1;
    swap(lsum[x],rsum[x]);
    swap(ch[x][0],ch[x][1]);
    Maintain(tl);
    Maintain(hd);
    return;
}

void Insert(int s,int k){
    int hd=Kth(s+1);
    int tl=Kth(s+2);
    Splay(hd,0);
    Splay(tl,hd);
    ch[tl][0]=Build(1,k);
    if(ch[tl][0])
        fa[ch[tl][0]]=tl;
    Maintain(tl);
    Maintain(hd);
    return;
}

void GetSum(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    printf("%d\n",sum[x]);
    return;
}

void GetMaxSum(){
    int hd=Kth(1);
    int tl=Kth(size[root]);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    printf("%d\n",msum[x]);
    return;
}

int main(){
    int pos,cnt,v;
    rep(i,1,500005)
        stk[++top]=i;
    rep(i,1,2)
        seq[i]=-0x2f2f2f2f;
    msum[0]=-0x2f2f2f2f;
    root=Build(1,2);
    Read(N);
    Read(M);
    rep(i,1,N)
        scanf("%d",&seq[i]);
    Insert(0,N);
    while(M--){
        scanf("%s",inst+1);
        if(inst[1]=='I'){
            Read(pos);
            Read(cnt);
            rep(i,1,cnt)
                scanf("%d",&seq[i]);
            Insert(pos,cnt);
        }
        else if(inst[1]=='D'){
            Read(pos);
            Read(cnt);
            Delete(pos,cnt);
        }
        else if(inst[1]=='R'){
            Read(pos);
            Read(cnt);
            Reverse(pos,cnt);
        }
        else if(inst[1]=='G'){
            Read(pos);
            Read(cnt);
            GetSum(pos,cnt);
        }
        else{
            if(inst[3]=='K'){
                Read(pos);
                Read(cnt);
                scanf("%d",&v);
                Modify(pos,cnt,v);
            }
            else
                GetMaxSum();
        }
    }
    return 0;
}