BZOJ 1500: [NOI2005]维修数列 (splay tree)

1500: [NOI2005]维修数列

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 4229 Solved: 1283
[Submit][Status]

Description

Input

输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。

Output

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

Sample Input

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

Sample Output

-1
10
1
10

HINT

Source

Splay

[Submit][Status]

HOME Back

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013/8/27 3:28:32

 File Name     :F:\2013ACM练习\专题学习\splay_tree_2\维修数列.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 #define Key_value ch[ch[root][1]][0]

 const int MAXN = ;

 const int INF = 0x3f3f3f3f;

 int pre[MAXN],ch[MAXN][],key[MAXN],size[MAXN];

 int root,tot1;

 int sum[MAXN],rev[MAXN],same[MAXN];

 int lx[MAXN],rx[MAXN],mx[MAXN];

 int s[MAXN],tot2;//内存池和容量

 int a[MAXN];

 int n,q;

 //debug部分**********************************

 void Treavel(int x)

 {

     if(x)

     {

         Treavel(ch[x][]);

         printf("结点：%2d: 左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d\n",x,ch[x][],ch[x][],pre[x],size[x]);

         Treavel(ch[x][]);

     }

 }

 void debug()

 {

     printf("root:%d\n",root);

     Treavel(root);

 }

 //以上是debug部分**************************************

 void NewNode(int &r,int father,int k)

 {

     if(tot2) r = s[tot2--];//取的时候是tot2--,存的时候就是++tot2

     else r = ++tot1;

     pre[r] = father;

     ch[r][] = ch[r][] = ;

     key[r] = k;

     sum[r] = k;

     rev[r] = same[r] = ;

     lx[r] = rx[r] = mx[r] = k;

     size[r] = ;

 }

 void Update_Rev(int r)

 {

     if(!r)return;

     swap(ch[r][],ch[r][]);

     swap(lx[r],rx[r]);

     rev[r] ^= ;

 }

 void Update_Same(int r,int v)

 {

     if(!r)return;

     key[r] = v;

     sum[r] = v*size[r];

     lx[r] = rx[r] = mx[r] = max(v,v*size[r]);

     same[r] = ;

 }

 void push_up(int r)

 {

     int lson = ch[r][], rson = ch[r][];

     size[r] = size[lson] + size[rson] + ;

     sum[r] = sum[lson] + sum[rson] + key[r];

     lx[r] = max(lx[lson],sum[lson] + key[r] + max(,lx[rson]));

     rx[r] = max(rx[rson],sum[rson] + key[r] + max(,rx[lson]));

     mx[r] = max(,rx[lson]) + key[r] + max(,lx[rson]);

     mx[r] = max(mx[r],max(mx[lson],mx[rson]));

 }

 void push_down(int r)

 {

     if(same[r])

     {

         Update_Same(ch[r][],key[r]);

         Update_Same(ch[r][],key[r]);

         same[r] = ;

     }

     if(rev[r])

     {

         Update_Rev(ch[r][]);

         Update_Rev(ch[r][]);

         rev[r] = ;

     }

 }

 void Build(int &x,int l,int r,int father)

 {

     if(l > r)return;

     int mid = (l+r)/;

     NewNode(x,father,a[mid]);

     Build(ch[x][],l,mid-,x);

     Build(ch[x][],mid+,r,x);

     push_up(x);

 }

 void Init()

 {

     root = tot1 = tot2 = ;

     ch[root][] = ch[root][] = size[root] = pre[root] = ;

     same[root] = rev[root] = sum[root] = key[root] = ;

     lx[root] = rx[root] = mx[root] = -INF;

     NewNode(root,,-);

     NewNode(ch[root][],root,-);

     for(int i = ;i < n;i++)

         scanf("%d",&a[i]);

     Build(Key_value,,n-,ch[root][]);

     push_up(ch[root][]);

     push_up(root);

 }

 //旋转,0为左旋，1为右旋

 void Rotate(int x,int kind)

 {

     int y = pre[x];

     push_down(y);

     push_down(x);

     ch[y][!kind] = ch[x][kind];

     pre[ch[x][kind]] = y;

     if(pre[y])

         ch[pre[y]][ch[pre[y]][]==y] = x;

     pre[x] = pre[y];

     ch[x][kind] = y;

     pre[y] = x;

     push_up(y);

 }

 //Splay调整，将r结点调整到goal下面

 void Splay(int r,int goal)

 {

     push_down(r);

     while(pre[r] != goal)

     {

         if(pre[pre[r]] == goal)

         {

             push_down(pre[r]);

             push_down(r);

             Rotate(r,ch[pre[r]][] == r);

         }

         else

         {

             push_down(pre[pre[r]]);

             push_down(pre[r]);

             push_down(r);

             int y = pre[r];

             int kind = ch[pre[y]][]==y;

             if(ch[y][kind] == r)

             {

                 Rotate(r,!kind);

                 Rotate(r,kind);

             }

             else

             {

                 Rotate(y,kind);

                 Rotate(r,kind);

             }

         }

     }

     push_up(r);

     if(goal == ) root = r;

 }

 int Get_kth(int r,int k)

 {

     push_down(r);

     int t = size[ch[r][]] + ;

     if(t == k)return r;

     if(t > k)return Get_kth(ch[r][],k);

     else return Get_kth(ch[r][],k-t);

 }

 //在第pos个数后面插入tot个数

 void Insert(int pos,int tot)

 {

     for(int i = ;i < tot;i++)scanf("%d",&a[i]);

     Splay(Get_kth(root,pos+),);

     Splay(Get_kth(root,pos+),root);

     Build(Key_value,,tot-,ch[root][]);

     push_up(ch[root][]);

     push_up(root);

 }

 //删除子树

 void erase(int r)

 {

     if(!r)return;

     s[++tot2] = r;

     erase(ch[r][]);

     erase(ch[r][]);

 }

 //从第pos个数开始连续删除tot个数

 void Delete(int pos,int tot)

 {

     Splay(Get_kth(root,pos),);

     Splay(Get_kth(root,pos+tot+),root);

     erase(Key_value);

     pre[Key_value] = ;

     Key_value = ;

     push_up(ch[root][]);

     push_up(root);

 }

 //将从第pos个数开始的连续的tot个数修改为c

 void Make_Same(int pos,int tot,int c)

 {

     Splay(Get_kth(root,pos),);

     Splay(Get_kth(root,pos+tot+),root);

     Update_Same(Key_value,c);

     push_up(ch[root][]);

     push_up(root);

 }

 //将第pos个数开始的连续tot个数进行反转

 void Reverse(int pos,int tot)

 {

     Splay(Get_kth(root,pos),);

     Splay(Get_kth(root,pos+tot+),root);

     Update_Rev(Key_value);

     push_up(ch[root][]);

     push_up(root);

 }

 //得到第pos个数开始的tot个数的和

 int Get_Sum(int pos,int tot)

 {

     Splay(Get_kth(root,pos),);

     Splay(Get_kth(root,pos+tot+),root);

     return sum[Key_value];

 }

 //得到第pos个数开始的tot个数中最大的子段和

 int Get_MaxSum(int pos,int tot)

 {

     Splay(Get_kth(root,pos),);

     Splay(Get_kth(root,pos+tot+),root);

     return mx[Key_value];

 }

 void InOrder(int r)

 {

     if(!r)return;

     push_down(r);

     InOrder(ch[r][]);

     printf("%d ",key[r]);

     InOrder(ch[r][]);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

      while(scanf("%d%d",&n,&q) == )

     {

         Init();

         char op[];

         int x,y,z;

         while(q--)

         {

             scanf("%s",op);

             if(strcmp(op,"INSERT") == )

             {

                 scanf("%d%d",&x,&y);

                 Insert(x,y);

             }

             else if(strcmp(op,"DELETE") == )

             {

                 scanf("%d%d",&x,&y);

                 Delete(x,y);

             }

             else if(strcmp(op,"MAKE-SAME") == )

             {

                 scanf("%d%d%d",&x,&y,&z);

                 Make_Same(x,y,z);

             }

             else if(strcmp(op,"REVERSE") == )

             {

                 scanf("%d%d",&x,&y);

                 Reverse(x,y);

             }

             else if(strcmp(op,"GET-SUM") == )

             {

                 scanf("%d%d",&x,&y);

                 printf("%d\n",Get_Sum(x,y));

             }

             else if(strcmp(op,"MAX-SUM") == )

                 printf("%d\n",Get_MaxSum(,size[root]-));

         }

     }

     return ;

 }

巴特西