[NOI2005]维护数列——平衡树观止

本题题解并不详细，不推荐大家看这一篇。

可以看这篇

题目描述

请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）

100%的数据中，任何时刻数列中最多含有 500 000 个数。

100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。

100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。

题解：

刷完普通平衡树，文艺平衡树板子后，本题纯靠自己想，用了3h打码，4h调试，共7h多终于AC了。

此题我认为堪称“平衡树观止”

题目就是这么地裸。但就是让你写不出来。

粗略地说一下splay题解：

要用到：

1.n+2个点，1，n+2是方便提取用的。

2.哨兵0号点，

3.每个点维护：fa,ch[2],sz,sum,val,lm,rm,ans最后三个是最大子段和用的。

和标记：chan,rev

4.用long long

知识点：

1.区间提取，l-1到根，r+1到根的右儿子。根右儿子的左子树就是操作区间。

2.区间打标记，直接打。

3.找区间左端点，右端点等，返回第k大位置节点编号。

显然不能直接把端点当做编号。因为根本不知道原始编号转到哪里去了。

4.pushdown时机：

pushdown本质是为了将序列保持真正的情况，所以一旦触及，必须pushdown，否则形态一变，子树一换，都完了。

每次查找kth的x，因为每次查找对应一次splay，必须一路上都pushdown，

并且影响的只有rt到x路径上的点，所以其他位置可以不用pushdown

子树内部也是不会动的，不用pushdown。

5.pushup时机：

本质是为了更新信息，所以一个节点变化了，或者其子树变化了，都要pushup

splay里面有，也是路径上改变的点都会pushup的。

另外，操作区间操作后，该子树可能有了变化，还要pushup（根右儿子），pushup（根），别的节点也不会被这次操作影响。

6.1号点和n+2号点。为了不影响答案（可能是负数），所以权值为-inf，并且这两个点一定要保证在区间的两端。

7.0号哨兵

因为我这里是钦定lm，rm，ans都必须选择一个。所以0号的rm，lm，ans都是-inf，才不会因为设成0而取不到负数答案。

8.卡空间（bzoj64MB）

而同一时刻最多500000个。必须垃圾回收，dp[N],dc

操作：

1.插入：直接插成一个链可以，但是之后复杂度并不优秀。

可以分治处理。每次插入mid递归l，mid-1和mid+1，r,数的高度就直接logn了。

开始的加入原数列也是。

对于新加入一些数，先像这样建成一棵树，然后类似区间提取pos，pos+1。

那么，pos+1左儿子就是新树根的fa了，直接嫁接上去。记得pushup（pos+1）与（pos）

见ins，pre函数

2.删除。区间提取、然后直接删除rt的右儿子的左儿子。

要先进入这个子树，放进回收池里。

3.修改。区间提取，直接改。

4.翻转。区间提取。翻转标记。

注意，必须打标记的同时，就要翻转儿子，交换lm，rm

因为虽然是懒标记，但是对于这个节点的影响必须处理。

否则splay时可能会出锅。

因为x左右儿子会有标记，但不翻转，然后rotate(x)会交换子树，pushup(y)就把没有真正正确的x曾经的子树信息记录上去了。

5.区间和。区间提取。直接返回sum

6.最大子段和。直接返回t[rt].ans

注意事项：

1.保护哨兵，保护哨兵，保护哨兵。

2.任何时候，在splay(x)之前，必须确定x路径上的所有点都pushdown了。

3.pushup中，t[x].ans情况较多，不要忘了可以是t[x].val

4.swap(lm,rm)别错了。

代码：

#include<bits/stdc++.h>
#define rs t[x].ch[1]
#define ls t[x].ch[0]
#define numb ch-'0'
#define ri register int
#define il inline
using namespace std;
typedef long long ll;
const int N=+;
const ll inf=(1LL*<<);
char ch;
il void rdint(int &x){
    x=;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*+numb);
    (fl==true)&&(x=-x);
}
il void rdll(ll &x){
    x=;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*+numb);
    (fl==true)&&(x=-x);
}
struct node{
    int ch[],fa;
    ll rm,lm,sum,ans;
    int rev;
    ll chan;
    ll val;
    int sz;
    void init(int f,ll v){
        fa=f,val=v;rm=v;lm=v,ans=v,sum=v;
        rev=,chan=inf;
        sz=;
    }
}t[N];
il ll Max(ll a,ll b){
    return a>b?a:b;
}
int dc,dp[N],pc;
int n,m,rt;
ll st[N];
il int nc(){
    int r=dc?dp[dc--]:++pc;
    memset(t+r,,sizeof (node));return r;
}
il void pushup(int x){
    t[x].sum=t[t[x].ch[]].sum+t[t[x].ch[]].sum+t[x].val;
    t[x].rm=Max(t[t[x].ch[]].rm,Max(t[t[x].ch[]].sum+t[x].val,t[t[x].ch[]].sum+t[x].val+t[t[x].ch[]].rm));
    t[x].lm=Max(t[t[x].ch[]].lm,Max(t[t[x].ch[]].sum+t[x].val,t[t[x].ch[]].sum+t[x].val+t[t[x].ch[]].lm));
    t[x].ans=Max(t[x].lm,t[x].rm);
    t[x].ans=Max(t[x].ans,Max(t[t[x].ch[]].rm+t[x].val+t[t[x].ch[]].lm,Max(t[t[x].ch[]].rm+t[x].val,t[x].val+t[t[x].ch[]].lm)));
    t[x].ans=Max(t[x].ans,Max(t[t[x].ch[]].ans,t[t[x].ch[]].ans));
    t[x].ans=Max(t[x].ans,t[x].val);//bug 2
    t[x].sz=t[t[x].ch[]].sz+t[t[x].ch[]].sz+;
}
il void pushdown(int x){
    if(t[x].chan!=inf){
        if(ls){
        t[ls].chan=t[x].chan;
        t[ls].val=t[x].chan;
        t[ls].sum=t[ls].val*t[ls].sz;
        t[ls].rm=t[ls].lm=t[ls].ans=t[ls].val>?t[ls].sum:t[ls].val;
        }
        if(rs){
        t[rs].chan=t[x].chan;
        t[rs].val=t[x].chan;
        t[rs].sum=t[rs].val*t[rs].sz;
        t[rs].rm=t[rs].lm=t[rs].ans=t[rs].val>?t[rs].sum:t[rs].val;
        }
        t[x].chan=inf;
    }
    if(t[x].rev){
        if(ls&&t[ls].val!=-inf){
        t[ls].rev^=;
        swap(t[ls].lm,t[ls].rm);//bug1
        }
        if(rs&&t[rs].val!=-inf){
        t[rs].rev^=;
        swap(t[rs].lm,t[rs].rm);//bug1
        }
        swap(ls,rs);
        t[x].rev=;
    }
}
il void rotate(int x){
    int y=t[x].fa,d=t[y].ch[]==x;
    t[t[y].ch[d]=t[x].ch[!d]].fa=y;
    t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[]==y]=x;
    t[t[x].ch[!d]=y].fa=x;
    pushup(y);
}
il void splay1(int x,int f){
    while(t[x].fa!=f){
        int y=t[x].fa,z=t[y].fa;
        if(z!=f){
            rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
        }
        rotate(x);
    }
    pushup(x);
    if(f==) rt=x;
}
il int kth(int k){
    int x=rt;
    while(){
        pushdown(x);
        int d=k-t[t[x].ch[]].sz;
        if(d<=) x=t[x].ch[];
        else if(d==) return x;
        else{
            k=d-;
            x=t[x].ch[];
        }
    }
}
int newrt;
il void splay2(int x,int f){
    while(t[x].fa!=f){
        int y=t[x].fa,z=t[y].fa;
        if(z!=f){
            rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
        }
        rotate(x);
    }
    pushup(x);
    if(f==) newrt=x;
}
il void build(ll v){
    if(!newrt){
        newrt=nc();
        t[newrt].init(,v);
        return;
    }
    int x=newrt;
    while(){
        if(!t[x].ch[]){
            t[x].ch[]=nc();
            t[t[x].ch[]].init(x,v);
            x=t[x].ch[];
            break;
        }
        x=t[x].ch[];
    }
    splay2(x,);
}
il int pre(int l,int r,int f){
    if(l>r){
        return ;
    }
    int mid=(l+r)>>;
    int x=nc();
    t[x].init(f,st[mid]);
    t[x].ch[]=pre(l,mid-,x);
    t[x].ch[]=pre(mid+,r,x);
    pushup(x);
    return x;
}
il void ins(int pos,int tot){
    newrt=;
    for(ri i=;i<=tot;i++){
        rdll(st[i]);
    }
    newrt=pre(,tot,);
    int x=kth(pos+);
    int y=kth(pos+);
    splay1(x,);
    splay1(y,x);
    t[y].ch[]=newrt;
    t[newrt].fa=y;
    pushup(y);
    pushup(x);
}
il void del(int x){
    if(t[x].ch[]) del(t[x].ch[]);
    dp[++dc]=x;
    if(t[x].ch[]) del(t[x].ch[]);
}
il void remove(int pos,int tot){
    int l=kth(pos);
    int r=kth(pos+tot+);
    splay1(l,);
    splay1(r,l);
    del(t[r].ch[]);
    t[r].ch[]=;
    pushup(r);
    pushup(l);
}
il void upda(int pos,int tot,ll c){
    int l=kth(pos);
    int r=kth(pos+tot+);
    splay1(l,);
    splay1(r,l);

    int x=t[r].ch[];
    t[x].chan=c;
    t[x].val=c;
    t[x].sum=t[x].val*t[x].sz;
    t[x].rm=t[x].lm=t[x].ans=t[x].val>?t[x].sum:t[x].val;

    pushup(r);
    pushup(l);
}
il void reverse(int pos,int tot){
    int l=kth(pos);
    int r=kth(pos+tot+);
    splay1(l,);
    splay1(r,l);

    int x=t[r].ch[];
    t[x].rev^=;
    swap(t[x].lm,t[x].rm);    

    pushup(r);
    pushup(l);
}
il ll qs(int pos,int tot){
    int l=kth(pos);
    int r=kth(pos+tot+);
    splay1(l,);
    splay1(r,l);

    int x=t[r].ch[];
    int ret=t[x].sum;
    pushdown(x);//bug 3
    splay1(x,);
    return ret;
}

int main()
{
    t[].lm=t[].rm=t[].ans=-inf;//warning warning warning !!!
    t[].sz=;t[].sum=;
    scanf("%d%d",&n,&m);
    st[]=-inf;
    for(int i=;i<=n+;i++){
        rdll(st[i]);
    }
    st[n+]=-inf;

    rt=pre(,n+,);
    char lp[];
    int pos,tot;
    ll c;
    int cnt=;
    for(ri i=;i<=m;i++){
        ch=getchar();
        while(ch>'Z'||ch<'A')ch=getchar();
        for(cnt=;(ch=='-')||(ch<='Z'&&ch>='A');ch=getchar())lp[++cnt]=ch;
        if(lp[]=='I'){
            rdint(pos),rdint(tot);
            if(tot==) continue;
            ins(pos,tot);
        }
        else if(lp[]=='D'){
            rdint(pos),rdint(tot);
            if(tot==) continue;
            remove(pos,tot);
        }
        else if(lp[]=='M'&&lp[]=='K'){
            rdint(pos),rdint(tot);rdll(c);
            if(tot==) continue;
            upda(pos,tot,c);
        }
        else if(lp[]=='M'&&lp[]=='X'){
            printf("%lld\n",t[rt].ans);
        }
        else if(lp[]=='G'){
            rdint(pos),rdint(tot);
            if(tot==) printf("0\n");
            else printf("%lld\n",qs(pos,tot));
        }
        else if(lp[]=='R'){
            rdint(pos),rdint(tot);
            if(tot==) continue;
            reverse(pos,tot);
        }
    }
    return ;
}

总结：

数据结构，就是利用一种结构，维护数的算法。通常为了减少时间复杂度，而牺牲一些空间作为代价。

就是在保证查询、修改正确的情况下，最大限度地减少时间复杂度。

为了保证复杂度，每个数据结构都有自己的方式。

splay平衡树结构的灵魂函数：splay，rotate

维护正确性并且节省时间的灵魂函数：pushdown，pushup

这四个函数写对，整个平衡数的框架就建立起来了。

将二者有机结合起来，就能够达到时间和正确性的统一。

数据结构基本都是这样。