NOI2005维修数列（splay）

题目描述：

Description

请写一个程序，要求维护一个数列，支持以下 6 种操作：

请注意，格式栏中的下划线‘ _ ’表示实际输入文件中的空格

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

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

解题思路：

听说出这道题时还没有splay，所以当时是块状链表题。

6种操作：

1.插入：

常规操作，将子树建好再把前驱后继中间空出来栽上，pushup两遍愈合即可。

PS：可以用建树时的build函数适配数组

2.删除：

将整棵树像挤痘痘一样挤出来扔掉。

PS：空间开不下，需要回收废树，不要将树分解，那样浪费时间，开一个栈，将废树压入，开新点时弹出一棵树，推入左右子树，根节点格式化输出即可。

3.修改：

常规操作，只不过用bool做懒惰标记主要是我怕它区间赋0

4.翻转：

文艺平衡树模板。

PS：pushdown时若有3的bool型标记就可以清除4的标记了。

5.求和：

维护一个sum

6.最大值：

类似vijos小白逛公园维护左连续最大值，右连续最大值，中间连续最大值即可。

PS：把0号节点的中间连续最大值赋为-_{∞，防止ans<0}

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lll tr[spc].ch[0]

 #define rrr tr[spc].ch[1]

 #define ls ch[0]

 #define rs ch[1]

 const int N=;

 struct trnt{

     int ch[];

     int fa;

     bool onmi;

     int lzt;

     int val;

     int sum;

     int wgt;

     int lmx,rmx,mmx;

     int chd;

 }tr[N];

 trnt stdtr;

 int n,m;

 int lne[N];

 int bin[N];

 int top=;

 int root;

 int siz;

 char cmd[];

 int ins[N];

 int org,fin;

 void destory(int &spc)

 {

     bin[++top]=spc;

     spc=;

     return ;

 }

 int translate(void)

 {

     int tmp=(int)(cmd[]);

     if(tmp=='S')

         return ;

     if(tmp=='L')

         return ;

     if(tmp=='K')

         return ;

     if(tmp=='V')

         return ;

     if(tmp=='T')

         return ;

     if(tmp=='X')

         return ;

        return ;

 }

 bool whc(int spc)

 {

     return tr[tr[spc].fa].rs==spc;

 }

 void pushup(int spc)

 {

     tr[spc].sum=tr[lll].sum+tr[rrr].sum+tr[spc].val;

     tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;

     tr[spc].lmx=std::max(tr[lll].lmx,tr[lll].sum+tr[spc].val+tr[rrr].lmx);

     tr[spc].rmx=std::max(tr[rrr].rmx,tr[rrr].sum+tr[spc].val+tr[lll].rmx);

     tr[spc].mmx=std::max(tr[spc].val+tr[lll].rmx+tr[rrr].lmx,std::max(tr[lll].mmx,tr[rrr].mmx));

     return ;

 }

 int apply()

 {

     if(top)

     {

         int spc=bin[top--];

         if(lll)

             bin[++top]=lll;

         if(rrr)

             bin[++top]=rrr;

         return spc;

     }

     return ++siz;

 }

 void address(int &spc)

 {

     spc=apply();

     tr[spc]=stdtr;

     return ;

 }

 void new_point(int &spc,int mid,int *a,int f)

 {

     address(spc);

     tr[spc].fa=f;

     tr[spc].val=a[mid];

     return ;

 }

 void din(int spc,int k)

 {

     if(!spc)

         return ;

     tr[spc].onmi=true;

     tr[spc].lzt=k;

     tr[spc].val=k;

     tr[spc].sum=tr[spc].wgt*k;

     tr[spc].mmx=(k>)?tr[spc].sum:k;

     tr[spc].lmx=tr[spc].rmx=(k>)?tr[spc].sum:;

     return ;

 }

 void ovt(int spc)

 {

     if(!spc)

         return ;

     tr[spc].chd^=;

     std::swap(lll,rrr);

     std::swap(tr[spc].lmx,tr[spc].rmx);

     return ;

 }

 void pushdown(int spc)

 {

     if(tr[spc].onmi)

     {

         din(lll,tr[spc].lzt);

         din(rrr,tr[spc].lzt);

         tr[spc].lzt=;

         tr[spc].chd=;

         tr[spc].onmi=false;

     }

     if(tr[spc].chd)

     {

         ovt(lll);

         ovt(rrr);

         tr[spc].chd=;

     }

     return ;

 }

 void rotate(int spc)

 {

     int f=tr[spc].fa;

     bool k=whc(spc);

     tr[f].ch[k]=tr[spc].ch[!k];

     tr[spc].ch[!k]=f;

     tr[tr[f].fa].ch[whc(f)]=spc;

     tr[spc].fa=tr[f].fa;

     tr[f].fa=spc;

     tr[tr[f].ch[k]].fa=f;

     pushup(f);

     pushup(spc);

     return ;

 }

 void splay(int spc,int f)

 {

     while(tr[spc].fa!=f)

     {

         int ft=tr[spc].fa;

         if(tr[ft].fa==f)

         {

             rotate(spc);

             break;

         }

         if(whc(spc)^whc(ft))

             rotate(spc);

         else

             rotate(ft);

         rotate(spc);

     }

     if(!f)

         root=spc;

     return ;

 }

 void build(int l,int r,int &spc,int f,int *a)

 {

     if(l>r)

         return ;

     int mid=(l+r)>>;

     new_point(spc,mid,a,f);

     if(l==r)

     {

         tr[spc].lmx=tr[spc].rmx=(a[mid]>)?a[mid]:;

         tr[spc].mmx=a[mid];

         tr[spc].wgt=;

         tr[spc].sum=a[mid];

         if(l==)

             org=spc;

            if(l==n+)

                fin=spc;

     }

     build(l,mid-,lll,spc,a);

     build(mid+,r,rrr,spc,a);

     pushup(spc);

     if(l==r)

         tr[spc].mmx=tr[spc].val;

     return ;

 }

 int place(int spc,int rnk)

 {

     pushdown(spc);

     if(tr[lll].wgt>=rnk)

         return place(lll,rnk);

     if(tr[lll].wgt+==rnk)

         return spc;

     return place(rrr,rnk-tr[lll].wgt-);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

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

     build(,n+,root,,lne);

     tr[].mmx=-0x3f3f3f3f;

     while(m--)

     {

         scanf("%s",cmd);

         int opr=translate();

         if(opr==)

         {

             int tmproot;

             int pos,tot;

             scanf("%d%d",&pos,&tot);

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

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

             build(,tot,tmproot,,ins);

             splay(place(root,pos+),);

             splay(place(root,pos+),root);

             tr[tr[root].rs].ls=tmproot;

             tr[tmproot].fa=tr[root].rs;

             pushup(tr[root].rs);

             pushup(root);

         }else if(opr==)

         {

             int pos,tot;

             scanf("%d%d",&pos,&tot);

             splay(place(root,pos),);

             splay(place(root,pos+tot+),root);

             destory(tr[tr[root].rs].ls);

             pushup(tr[root].rs);

             pushup(root);

         }else if(opr==)

         {

             int pos,tot,c;

             scanf("%d%d%d",&pos,&tot,&c);

             splay(place(root,pos),);

             splay(place(root,pos+tot+),root);

             pushdown(root);

             pushdown(tr[root].rs);

             int spc=tr[tr[root].rs].ls;

             din(spc,c);

             pushup(tr[root].rs);

             pushup(root);

         }else if(opr==)

         {

             int pos,tot;

             scanf("%d%d",&pos,&tot);

             splay(place(root,pos),);

             splay(place(root,pos+tot+),root);

             pushdown(root);

             pushdown(tr[root].rs);

             int spc=tr[tr[root].rs].ls;

             ovt(spc);

             pushup(tr[root].rs);

             pushup(root);

         }else if(opr==)

         {

             int pos,tot;

             scanf("%d%d",&pos,&tot);

             splay(place(root,pos),);

             splay(place(root,pos+tot+),root);

             int spc=tr[tr[root].rs].ls;

             printf("%d\n",tr[spc].sum);

         }else{

             splay(place(root,),);

             splay(place(root,tr[root].wgt),root);

             printf("%d\n",tr[tr[tr[root].rs].ls].mmx);

         }

     }

     return ;

 }

-∞

巴特西