edward_mj

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1493

【算法分析】

这题一开始被那个翻转给吓到了，但是画了个图以后发现只是将顺时针变成逆时针，位置全变成n+2-i而已。假如我们都当成是未翻转前去看的话，就很容易想到维护方法。

定义一个偏移量pyl（拼音= =），表示向右旋转了多少格。在搞一个bool型表示是否翻转。

然后翻转前的R操作，直接偏移量+x

如果是翻转后的话，那么就是-x，因为数字变逆时针了，你要全部当成翻转前的情况的话，就相当于逆时针转动。（画了图就比较好理解）

然后有了这些性质，就维护一棵线段树即可。

另外注意数组里的color和线段树里的同步问题。

总之就是一些细节的东西。

【其它】1A，居然垫底了

Rank Run ID User Memory Time Language Code Length Submit Time 1 5318 root 18164K 2839MS Pascal 5.70K 2009-07-08 11:37:16 2 8949 oimaster 29172K 3514MS Pascal 5.26K 2010-01-30 11:57:51 3 5545 pyf 24144K 3948MS Pascal 5.17K 2009-07-10 20:11:20 4 9596 sadness 26860K 4107MS G++ 6.31K 2010-02-18 20:57:45 5 5942 tracyhenry 37808K 4342MS Pascal 4.89K 2009-08-04 15:24:39 6 9366 lilymona 41140K 4592MS G++ 2.69K 2010-02-11 02:14:30 7 5547 xlmj531 17064K 4608MS Pascal 5.92K 2009-07-10 20:14:23 8 5544 tclsm1991 23176K 4686MS Pascal 7.96K 2009-07-10 20:09:27 9 5542 tclsm 23168K 4840MS Pascal 7.96K 2009-07-10 20:08:04 10 5828 wu3412790 44288K 4871MS Pascal 3.55K 2009-07-18 22:11:15 11 9641 edward_mj 30800K 4873MS G++ 4.13K 2010-02-19 21:25:25

【CODE】

#include

维护数列

【问题描述】

请写一个程序，要求维护一个数列，支持以下 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;
        }
    }
}

【算法分析】

以前用SBT做过了，不过为了学习Splay，又用它来做测试了。。。

第一次写Splay，先写了个非指针版的。。。一直WA，后来模范beyondvoid大牛的一些技巧，写了个指针版的才AC。。。

【其它】

居然比SBT快。。。

不过SBT以前用pascal写的，现在是C++，另外我觉得我的SBT使用递归也是一个重要原因吧。

【CODE】

#include const int inf=1000000000;
int limit,ss;
struct Splaytype{
    struct Splaynode{
        Splaynode *l,*r,*fa;
        int key,s;
    };   
   
    Splaynode space[1000000],*root,*p,*q,*null;
    int tot;
    void init(){
        null=&space[0];
        null->l=null;
        null->r=null;
        null->fa=null;
        null->s=0;
        tot=1;
        Splaynode *p=&space[tot];
        p->l=null;
        p->r=null;
        p->fa=null;
        p->key=inf;
        p->s=1;
        root=p;
    }   
   
    inline void update(Splaynode *x){
        if (x==null) return;
        x->s=x->l->s+x->r->s+1;
    }   
   
    void zag(Splaynode *x){
        Splaynode *y=x->fa;
        y->r=x->l;
        x->l=y;
        if (y->fa->l==y) y->fa->l=x;
                    else y->fa->r=x;
        x->fa=y->fa;
        y->fa=x;
        y->r->fa=y;
        update(y);
        update(x);
    }   
   
    void zig(Splaynode *x){
        Splaynode *y=x->fa;
        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;
        y->fa=x;
        y->l->fa=y;
        update(y);
        update(x);
    }   
   
    void Splay(Splaynode *x,Splaynode *pos){
        if (x==root) return;
        Splaynode *y,*z;
        while (x->fa!=pos){
            y=x->fa; z=y->fa;
            if (z==pos)
              if (y->l==x) zig(x);
                      else zag(x);
            else if (z->l==y)
              if (y->l==x) {zig(y); zig(x);}
                      else {zag(x); zig(x);}
            else
              if (y->r==x) {zag(y); zag(x);}
                      else {zig(x); zag(x);}
        }
    }   
   
    void ins(int key){
        p=root->l,q=root;
        for (;;){
            if (p==null){
                p=&space[++tot];
                p->l=null;
                p->r=null;
                p->s=1;
                p->key=key;
                p->fa=q;
                if (key                           else q->r=p;
                break;
            }else
            if (key                q=p;
                p=p->l;
            }   
            else{
                q=p;
                p=p->r;
            }   
        }
        q=p;
        for (;p!=null;p=p->fa) update(p);
        Splay(q,root);
    }   
   
    void del(){
        p=root->l; q=root;
        for (;;){
            if (p==null){
                Splay(q,root);
                if (q->key+ss                    root->l=q->r;
                    if (q->r!=null) q->r->fa=root;
                    update(root);
                }
                else{
                    q->l=null;
                    update(q);
                    update(root);
                }   
                return;
            }else
            if (p->key+ss>=limit){
                q=p;
                p=p->l;
            }   
            else{
                q=p;
                p=p->r;
            }   
        }   
    }
   
    int get(int rank){
        if (rank>root->s) return -1;
        int done=0,td;
        p=root;
        for (;;){
            if (done+p->r->s+1==rank) return p->key+ss;
            if (done+p->r->s+1>rank) p=p->r;
            else{
                done+=p->r->s+1;
                p=p->l;
            }   
        }   
    }   
}Splay;

int main(){
    freopen("cashier.in","r",stdin);
    freopen("cashier.out","w",stdout);
    Splay.init();
    int n,x,innum=1; char ch;
    scanf("%d%d",&n,&limit);
    for (int i=1;i<=n;i++){
        for (ch=getchar();ch==’ ‘ || ch==’n’;ch=getchar());
        scanf("%d",&x);
        switch (ch){
            case ‘I’:if (x            case ‘A’:ss+=x; Splay.del(); break;
            case ‘S’:ss-=x; Splay.del(); break;
            case ‘F’:printf("%dn",Splay.get(x+1)); break;
        }   
    }   
    printf("%dn",innum-Splay.root->s);
}