[NOI2005 day1 维护数列]Splay、平衡树上的线段树**

维护数列

【问题描述】

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

操作编号 输入文件中的格式

说明

1. 插入

INSERT_posi_tot_c1_c2_…_ctot

在当前数列的第 posi 个数字后插入 tot

个数字：c1, c2, …, ctot；若在数列首插

入，则 posi 为 0

2. 删除

DELETE_posi_tot

从当前数列的第 posi 个数字开始连续

删除 tot 个数字

3. 修改

MAKE-SAME_posi_tot_c

将当前数列的第 posi 个数字开始的连

续 tot 个数字统一修改为 c

4. 翻转

REVERSE_posi_tot

取出从当前数列的第 posi 个数字开始

的 tot 个数字，翻转后放入原来的位置

5. 求和

GET-SUM_posi_tot

计算从当前数列开始的第 posi 个数字

开始的 tot 个数字的和并输出

6. 求和最

大的子列

MAX-SUM

求出当前数列中和最大的一段子列，

并输出最大和

【输入格式】

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

第 2 行包含 N 个数字，描述初始时的数列。

以下 M 行，每行一条命令，格式参见问题描述中的表格。

【输出格式】

对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。

【输入样例】

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

【输出样例】

-110110

【样例说明】

初始时，我们拥有数列 2 -6 3 5 1 -5 -3 6 3

执行操作 GET-SUM 5 4，表示求出数列中从第 5 个数开始连续 4 个数字之和，1+(-5)+(-3)+6 = -1：

2 -6 3 5 1 -5 -3 6 3

执行操作 MAX-SUM，表示要求求出当前数列中最大的一段和，应为 3+5+1+(-5)+(-3)+6+3 = 10：

2 -6 3 5 1 -5 -3 6 3

执行操作 INSERT 8 3 -5 7 2，即在数列中第 8 个数字后插入-5 7 2，

2 -6 3 5 1 -5 -3 6 -5 7 2 3

执行操作 DELETE 12 1，表示删除第 12 个数字，即最后一个：

2 -6 3 5 1 -5 -3 6 -5 7 2

执行操作 MAKE-SAME 3 3 2，表示从第 3 个数开始的 3 个数字，统一修改为 2：

2 -6 3 5 1 -5 -3 6 -5 7 2

改为

2 -6 2 2 2 -5 -3 6 -5 7 2

执行操作 REVERSE 3 6，表示取出数列中从第 3 个数开始的连续 6 个数：

2 -6 2 2 2 -5 -3 6 -5 7 2

如上所示的灰色部分 2 2 2 -5 -3 6，翻转后得到 6 -3 -5 2 2 2，并放回原来位置：

2 -6 6 -3 -5 2 2 2 -5 7 2

最后执行 GET-SUM 5 4 和 MAX-SUM，不难得到答案 1 和 10。

2 -6 6 -3 -5 2 2 2 -5 7 2

【评分方法】

本题设有部分分，对于每一个测试点：

• 如果你的程序能在输出文件正确的位置上打印 GET-SUM 操作的答案，你可以得到该测试点 60%的分数；
• 如果你的程序能在输出文件正确的位置上打印 MAX-SUM 操作的答案，你可以得到该测试点 40%的分数；
• 以上两条的分数可以叠加，即如果你的程序正确输出所有 GET-SUM 和MAX-SUM 操作的答案，你可以得到该测试点 100%的分数。

请注意：如果你的程序只能正确处理某一种操作，请确定在输出文件正确的位置上打印结果，即必须为另一种操作留下对应的行，否则我们不保证可以正确评分。

【数据规模和约定】

• 你可以认为在任何时刻，数列中至少有 1 个数。
• 输入数据一定是正确的，即指定位置的数在数列中一定存在。

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

• 100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
• 100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件大小不超过 20MBytes。

【题目大意】

给定一个数列，有插入数列，删除区间，区间修改为同一个值，区间翻转，求区间和，求整个数列的最大子段和这几个操作。

【算法分析】

号称历年NOI最BT的数据结构题。

利用Splay，把要操作的区间的前驱和后继分别Splay到根和根的右结点，然后中间的部分就会聚集在根的右结点的左子树下。这样就可以进行想要的操作了。。。

然后剩下的各种操作的维护的话，你可以把这棵平衡树当成线段树来处理，不过多了一个当前结点，复杂了很多。。。

【其它】

开始在SBT上搞了个类似Splay的操作。。。但是老WA，后来想想还是直接Splay吧。。。

这题做了一整天…速度和beyondvoid的差不多，= =也许是因为我基本上模仿他的吧~

不过那个pushdown确实精妙。。。update的话，我是把维护父亲这一项都搞进去了。。。管他是不是都update一下。另外要注意的，pushdown以后的ml，mr，ms才是可用的。否则可能是虚假的。。。所以我在update里加了pushdown。另外比较猥琐的是第二个数据的话，有一个时刻数列中的数权<0，这样那个ms就要注意一下不能取null里的0值了，注意一下就成。

【CODE】

#include #include using namespace std;
const int inf=500000000;
int a[500001];

struct Splaytype{
    struct Node{
        Node *l,*r,*fa;
        int s,ms,ml,mr,sum,sn,key; // sn for samenum    mx for max_x
        bool same,rev;
    };
    Node *root,*null,sp[4000111];
    int tot;

    void update(Node *x){
        if (x==null) return;
        bool l=false,r=false;
        if (x->l!=null) {l=true; x->l->fa=x; pushdown(x->l);}
        if (x->r!=null) {r=true; x->r->fa=x; pushdown(x->r);}
        x->s=x->l->s+x->r->s+1;
        x->sum=x->l->sum+x->r->sum+x->key;
        x->ms=x->key;
        if (l) x->ms=max(x->ms,x->l->ms);
        if (r) x->ms=max(x->ms,x->r->ms);
        if (l) x->ms=max(x->ms,x->l->mr+x->key);
        if (r) x->ms=max(x->ms,x->r->ml+x->key);
        if (l && r) x->ms=max(x->ms,x->l->mr+x->r->ml+x->key);
        x->ml=x->l->sum+x->key;
        if (l) x->ml=max(x->ml,x->l->ml);
        if (r) x->ml=max(x->ml,x->l->sum+x->key+x->r->ml);
        x->mr=x->r->sum+x->key;
        if (r) x->mr=max(x->mr,x->r->mr);
        x->mr=max(x->mr,x->r->sum+x->key+x->l->mr);
    }

    void pushdown(Node *x){
        if (x==null) return;
        if (x->rev){
            x->rev=false;
            swap(x->l,x->r);
            if (x->l!=null) x->l->rev=!x->l->rev;
            if (x->r!=null) x->r->rev=!x->r->rev;
            swap(x->ml,x->mr);
        }
        if (x->same){
            x->same=false;
            if (x->l!=null) {x->l->same=true; x->l->sn=x->sn;}
            if (x->r!=null) {x->r->same=true; x->r->sn=x->sn;}
            x->key=x->sn;
            x->sum=x->s*x->key;
            x->ms=x->ml=x->mr=max(x->sum,x->key);
        }
    }

    void rotate(Node *x,char op){
        Node *y=x->fa;
        if (op==’l’){y->r=x->l; x->l=y;}
                else{y->l=x->r; x->r=y;}
        if (y->fa->l==y) y->fa->l=x;
                     else y->fa->r=x;
        x->fa=y->fa;
        update(y);
        update(x);
    }

    Node* newnode(int key){
        Node *p=&sp[++tot];
        p->l=null; p->r=null; p->fa=null;
        p->s=1; p->ms=p->ml=p->mr=p->sum=p->key=key;
        p->sn=0; p->same=false; p->rev=false;
        return p;
    }

    void init(){
        Node *p,*q;
        tot=0;
        null=&sp[0];
        null->l=null; null->r=null; null->fa=null;
        null->s=null->ms=null->ml=null->mr=null->sum=null->sn=0;
        null->same=null->rev=false; null->key=0;
        root=newnode(-inf);
        p=newnode(-inf);
        q=newnode(-inf);
        root->l=q;
        q->l=p;
        update(q);
        update(root);
    }

    void Splay(Node *x,Node *pos){
        if (x==null || x==pos) return;
        pushdown(x);
        Node *y,*z;
        while (x->fa!=pos){
            y=x->fa; z=y->fa;
            if (z==pos)
              if (y->l==x) rotate(x,’r’);
                      else rotate(x,’l’);
            else if (z->l==y)
              if (y->l==x) {rotate(y,’r’); rotate(x,’r’);}
                      else {rotate(x,’l’); rotate(x,’r’);}
            else
              if (y->r==x) {rotate(y,’l’); rotate(x,’l’);}
                      else {rotate(x,’r’); rotate(x,’l’);}
        }
    }

    Node* findpos(int pos){
        int done=0;
        Node *p=root;
        for (;;){
            pushdown(p);
            if (done+p->l->s+1==pos) return p;
            if (done+p->l->s+1                               else p=p->l;
        }
    }

    void ins(int st,int n){
        st=min(st,root->s-2);
        Node *p=findpos(st),*q=findpos(st+1),*tmp;
        Splay(p,root);
        Splay(q,p);
        for (int i=1;i<=n;i++){
            tmp=newnode(a[i]);
            if (i        }
        for (int i=1;i            tmp=&sp[tot-i];
            update(tmp);
        }
        q->l=tmp;
        update(q);
        update(p);
        update(root);
    }

    void del(int l,int r){
        r=min(r,root->s-2);
        Node *p=findpos(l-1),*q=findpos(r+1);
        Splay(p,root);
        Splay(q,p);
        q->l=null;
        update(q);
        update(p);
        update(root);
    }

    void makesame(int l,int r,int C){
        r=min(r,root->s-2);
        Node *p=findpos(l-1),*q=findpos(r+1);
        Splay(p,root);
        Splay(q,p);
        q->l->same=true;
        q->l->sn=C;
        update(q);
        update(p);
        update(root);
    }

    void reverse(int l,int r){
        r=min(r,root->s-2);
        Node *p=findpos(l-1),*q=findpos(r+1);
        Splay(p,root);
        Splay(q,p);
        q->l->rev=true;
        update(q);
        update(p);
        update(root);
    }

    int getsum(int l,int r){
        r=min(r,root->s-2);
        Node *p=findpos(l-1),*q=findpos(r+1);
        Splay(p,root);
        Splay(q,p);
        pushdown(q->l);
        return q->l->sum;
    }
}Splay;

int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    Splay.init();
    char op[100]; int n,m,pos;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    Splay.ins(1,n);
    for (int i=1;i<=m;i++){
        scanf("%s",&op);
        switch (op[0]){
            case ‘I’:
                scanf("%d%d",&pos,&n);
                for (int i=1;i<=n;i++) scanf("%d",&a[i]);
                Splay.ins(pos+1,n);
                break;
            case ‘D’:
                scanf("%d%d",&pos,&n);
                Splay.del(pos+1,pos+n);
                break;
            case ‘M’:
                if (op[2]==’K’){
                  int C;
                  scanf("%d%d%d",&pos,&n,&C);
                  Splay.makesame(pos+1,pos+n,C);
                }
                else{
                    Splay.pushdown(Splay.root);
                    printf("%dn",Splay.root->ms);
                }
                break;
            case ‘R’:
                scanf("%d%d",&pos,&n);
                Splay.reverse(pos+1,pos+n);
                break;
            case ‘G’:
                scanf("%d%d",&pos,&n);
                printf("%dn",Splay.getsum(pos+1,pos+n));
                break;
        }
    }
}