[关闭]
@Bei-S 2019-01-10T07:10:33.000000Z 字数 13544 阅读 1576

Splay学习笔记

数据结构

最怕一生碌碌无为，还安慰自己平凡可贵。

平衡树就是防止2X查找树的树高过高导致复杂度过大

Splay是一种用来解决平衡树问题的算法，但是常数较大(和Treap相比)

但是他的旋转操作在LCT中便有了用武之地

Splay用处：

1.区间（序列）操作

可以用来进行区间操作，每次splay前驱后继即可
很重要的一个就是区间翻转(翻转标记！！！)
还有Split！！！

2.记录子树信息

懒标记，最大值，子树和....

3.区间

Splay基本操作：

1.Update：

主要是用来更新父亲节点信息，例如sum，size之类的

  1. inline void update(int x){
  2.   siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x];
  3. }

2.Rotate

用来翻转节点,具体过程推荐自己手画几遍最好

  1. inline void rotate(int x){
  2.     int y=f[x],z=f[y],t=son[y][0]==x;
  3.     if(z) son[z][son[z][1]==y]=x;f[x]=z;
  4.     son[y][!t]=son[x][t];f[son[x][t]]=y;
  5.     son[x][t]=y;f[y]=x;
  6.     update(y);update(x);
  7. }

3.Splay

把一个节点旋转到另一个节点下方

我们定义A为父亲和爷爷的大小关系以及B为父亲和儿子的大小关系

这里主要是分两种情况

1.当A==B，即三者在同一条链上时，我们先翻转父亲，再翻转儿子，可以降低树高（当链长较长时）

2.当A!=B,翻转两次儿子即可

  1. inline void splay(int x,int s){
  2.     while(f[x]!=s){
  3.         int y=f[x],z=f[y];
  4.         if(z!=s) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
  5.         rotate(x);
  6.     }
  7.     if(!s) rt=x;
  8. }

4.Find(Rank)

主要用来找到第x个数的位置
当我们找到x时，把它splay到根，这时它左子树大小就是它的排名了辣
（这种写法要加入两个虚点，要不首尾节点没有前驱后继了）

  1. inline void find(int x){
  2.     int s=rt;
  3.     if(s==0) return;
  4.     while(son[s][x>w[s]]&&w[s]!=x) s=son[s][x>w[s]];
  5.     splay(s,0);
  6. }

5.前驱后继

先把x旋转到根，那前驱就是它左儿子的最右儿子了
后继就是右儿子最左儿子

  1. inline int suf(int x){
  2.     find(x);
  3.     int s=rt;
  4.     if(w[s]>x) return s;
  5.     s=son[s][1];
  6.     while(son[s][0]) s=son[s][0];
  7.     return s;
  8. }
  10. inline int pre(int x){
  11.     find(x);
  12.     int s=rt;
  13.     if(w[s]<x) return s;
  14.     s=son[s][0];
  15.     while(son[s][1]) s=son[s][1];
  16.     return s;
  17. }

6.Insert

先找到它的位置，如果有了直接num++，否则新建一个节点

  1. inline void insert(int x){
  2.     int s=rt,fa=0;
  3.     while(s&&w[s]!=x) fa=s,s=son[s][x>w[s]];
  4.     if(s) num[s]++;
  5.     else {
  6.         s=++tot;
  7.         if(fa) son[fa][x>w[fa]]=s;
  8.         w[s]=x;
  9.         siz[s]=num[s]=1;
  10.         son[s][0]=son[s][1]=0;
  11.         f[s]=fa;
  12.     }
  13.     splay(s,0);
  14. }

7.Delete

我们找到x的前驱和后继
把前驱旋转到根，
然后把后继旋转成前驱的儿子，
此时的话后继的左儿子一定是我们要的数(考虑一下为什么)。
直接删除即可（注意要清除信息）

  1. inline void del(int x){
  2.     int pe=pre(x),sf=suf(x);
  3.     splay(pe,0);
  4.     splay(sf,pe);
  5.     int s=son[sf][0];
  6.     if(num[s]>1) {
  7.         num[s]--;
  8.         splay(s,0);
  9.     }
  10.     else son[sf][0]=0;
  11. }

8.Kth

求第k大和线段树操作有点类似，我们直接类似二分的概念直接找即可

  1. inline int kth(int x){
  2.     int s=rt;
  3.     while(1){
  4.         if(siz[son[s][0]]+num[s]<x) x-=siz[son[s][0]]+num[s],s=son[s][1];
  5.         else 
  6.         if(siz[son[s][0]]>=x) s=son[s][0];
  7.         else return w[s];
  8.     }
  9. }

9.Split

这个就是把需要操作序列的前驱和后继splay一下，这样直接对整段序列进行操作啦

  1. inline int split(int k,int tot){
  2.     int x=find(k),y=find(k+tot+1);
  3.     splay(x,0);
  4.     splay(y,x);
  5.     return son[y][0];
  6. }

Talk is cheat,show you the code:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N=1e5+7;
  5. const int inf=0x7ffffff;
  7. int son[N][2],rt,f[N],siz[N],w[N],tot,num[N];
  9. inline void update(int x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x];}
  11. inline void rotate(int x){
  12.     int y=f[x],z=f[y],t=son[y][0]==x;
  13.     if(z) son[z][son[z][1]==y]=x;f[x]=z;
  14.     son[y][!t]=son[x][t];f[son[x][t]]=y;
  15.     son[x][t]=y;f[y]=x;
  16.     update(y);update(x);
  17. }
  19. inline void splay(int x,int s){
  20.     if(!s) rt=x;
  21.     while(f[x]!=s){
  22.         int y=f[x],z=f[y];
  23.         if(z!=s) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
  24.         rotate(x);
  25.     }
  26. }
  28. inline void find(int x){
  29.     int s=rt;
  30.     if(s==0) return;
  31.     while(son[s][x>w[s]]&&w[s]!=x) s=son[s][x>w[s]];
  32.     splay(s,0);
  33. }
  35. inline int suf(int x){
  36.     find(x);
  37.     int s=rt;
  38.     if(w[s]>x) return s;
  39.     s=son[s][1];
  40.     while(son[s][0]) s=son[s][0];
  41.     return s;
  42. }
  44. inline int pre(int x){
  45.     find(x);
  46.     int s=rt;
  47.     if(w[s]<x) return s;
  48.     s=son[s][0];
  49.     while(son[s][1]) s=son[s][1];
  50.     return s;
  51. }
  53. inline void insert(int x){
  54.     int s=rt,fa=0;
  55.     while(s&&w[s]!=x) fa=s,s=son[s][x>w[s]];
  56.     if(s) num[s]++;
  57.     else {
  58.         s=++tot;
  59.         if(fa) son[fa][x>w[fa]]=s;
  60.         w[s]=x;
  61.         siz[s]=num[s]=1;
  62.         son[s][0]=son[s][1]=0;
  63.         f[s]=fa;
  64.     }
  65.     splay(s,0);
  66. }
  68. inline void del(int x){
  69.     int pe=pre(x),sf=suf(x);
  70.     splay(pe,0);
  71.     splay(sf,pe);
  72.     int s=son[sf][0];
  73.     if(num[s]>1) {
  74.         num[s]--;
  75.         splay(s,0);
  76.     }
  77.     else son[sf][0]=0;
  78. }
  80. inline int kth(int x){
  81.     int s=rt;
  82.     while(1){
  83.         if(siz[son[s][0]]+num[s]<x) x-=siz[son[s][0]]+num[s],s=son[s][1];
  84.         else 
  85.         if(siz[son[s][0]]>=x) s=son[s][0];
  86.         else return w[s];
  87.     }
  88. }
  90. template<class T>
  91. inline void read(T &num){
  92.     T x=0,f=1;char ch=getchar();
  93.     while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  94.     while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  95.     num=f*x;
  96. }
  98. int main()
  99. {   
  100.     int n;
  101.     read(n);
  102.     insert(inf-1);
  103.     insert(-inf+1);
  104.     while(n--)
  105.     {
  106.         int op,x;
  107.         read(op),read(x);
  108.         if(op==1)
  109.             insert(x);
  110.         if(op==2)
  111.             del(x);
  112.         if(op==3)
  113.             find(x),printf("%d\n",siz[son[rt][0]]);
  114.         if(op==4)
  115.             printf("%d\n",kth(x+1));
  116.         if(op==5)
  117.             printf("%d\n",w[pre(x)]);
  118.         if(op==6)
  119.             printf("%d\n",w[suf(x)]);
  120.     }
  121. }

还有一份不需要虚点，直接求rank和前驱后继的代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N=1e5+7;
  5. const int inf=0x7ffffff;
  7. int num[N],f[N],siz[N],son[N][2],w[N];
  9. int tot,n,m,rt;
  11. inline void update(int x) {siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x];}
  13. void rtt(int x){
  14.     int y=f[x],z=f[y],t=(son[y][0]==x);
  15.     if(z) son[z][son[z][1]==y]=x;
  16.     f[x]=z;
  18.     son[y][!t]=son[x][t];
  19.     f[son[x][t]]=y;
  21.     son[x][t]=y;
  22.     f[y]=x;
  24.     update(y);
  25.     update(x);
  26. }
  28. void splay(int x,int s){
  29.     while(f[x]!=s){
  30.         int y=f[x],z=f[y];
  31.         if(z!=s){
  32.             if( (son[y][0]==x)^(son[z][0]==y) ) rtt(x);
  33.             else rtt(y);
  34.         }
  35.         rtt(x);
  36.     }
  37.     if(!s) rt=x;
  38. }
  40. inline void insert(int &x,int fa,int v){
  41.     if(!x){
  42.         x=++tot;
  43.         f[x]=fa;
  44.         w[x]=v;
  45.         siz[x]=num[x]=1;
  46.         son[x][0]=son[x][1]=0;
  47.         splay(x,0);
  48.         return;
  49.     }
  50.     if(w[x]==v){
  51.         siz[x]++;
  52.         num[x]++;
  53.         splay(x,0);
  54.         return;
  55.     }
  56.     insert(son[x][v>w[x]],x,v);
  57.     update(x);
  58. }
  60. int get(int x){
  61.     int s=rt;
  62.     while(w[s]!=x&&s) s=son[s][x>w[s]];
  63.     return s;
  64. }
  66. int rank(int x){
  67.     int s=rt,ret=0;
  68.     int fa;
  69.     while(s){
  70.         if(x<=w[s]) fa=s,s=son[s][0];
  71.         else{
  72.             fa=s;
  73.             ret+=siz[son[s][0]]+num[s];
  74.             s=son[s][1];
  75.         }
  76.     }
  77.     splay(fa,0);
  78.     return ret+1;
  79. }
  81. int kth(int x){
  82.     int s=rt;
  83.     int fa=0;
  84.     while(x<=siz[son[s][0]]||x>siz[son[s][0]]+num[s]){
  85.         if(x<=siz[son[s][0]]) {
  86.             fa=s;
  87.             s=son[s][0];
  88.         }
  89.         else{
  90.             fa=s;
  91.             x-=siz[son[s][0]]+num[s];
  92.             s=son[s][1];
  93.         }
  94.     }
  95.     if(fa!=0) splay(fa,0);
  96.     return w[s];
  97. }
  99. void del(int x){
  100.     x=get(x);
  101.     if(!x) return;
  102.     splay(x,0);
  103.     if(num[x]>1) {
  104.         num[x]--;
  105.         siz[x]--;
  106.         return;
  107.     }
  108.     if(!son[x][0]||!son[x][1]) {
  109.         rt=son[x][0]+son[x][1];
  110.     }
  111.     else{
  112.         int y=son[x][1];
  113.         while(son[y][0]) y=son[y][0];
  114.         splay(y,x);
  115.         son[y][0]=son[x][0];
  116.         f[son[x][0]]=y;
  117.         rt=y;
  118.     }
  119.     update(rt);
  120.     f[rt]=0;
  121. }
  123. int pre(int x){
  124.     int s=rt,ret=-inf,fa;
  125.     while(s){
  126.         if(x<=w[s]) fa=s,s=son[s][0];
  127.         else fa=s,ret=max(ret,w[s]),s=son[s][1];
  128.     }
  129.     splay(fa,0);
  130.     return ret;
  131. }
  133. int suf(int x){
  134.     int s=rt,ret=inf,fa;
  135.     while(s){
  136.         if(x<w[s]) fa=s,ret=min(ret,w[s]),s=son[s][0];
  137.         else fa=s,s=son[s][1];
  138.     }
  139.     splay(fa,0);
  140.     return ret;
  141. }
  143. template<class T>
  144. inline void read(T &num){
  145.     T x=0,f=1;char ch=getchar();
  146.     while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  147.     while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  148.     num=f*x;
  149. }
  151. int main()
  152. {   
  153.     int n;
  154.     read(n);
  155.     while(n--)
  156.     {
  157.         int op,x;
  158.         read(op),read(x);
  159.         if(op==1)
  160.             insert(rt,0,x);
  161.         if(op==2)
  162.             del(x);
  163.         if(op==3)
  164.             printf("%d\n",rank(x));
  165.         if(op==4)
  166.             printf("%d\n",kth(x));
  167.         if(op==5)
  168.             printf("%d\n",pre(x));
  169.         if(op==6)
  170.             printf("%d\n",suf(x));
  171.     }
  172. }

还有用树状数组的[自己YY的，复杂度最坏应该多个log]

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. #define lowbit(x) x & -x
  5. #define mid ((l+r)>>1)
  7. const int N=1e5+7;
  9. int opt[N],a[N],b[N],n,cnt,m;
  11. int s[N];
  13. inline void add(int x,int y){
  14.     while(x<=m){
  15.         s[x]+=y;
  16.         x+=lowbit(x);
  17.     }
  18. }
  20. inline int sa(int x){
  21.     int sum=0;
  22.     while(x){
  23.         sum+=s[x];
  24.         x-=lowbit(x);
  25.     }
  26.     return sum;
  27. }
  29. inline int gt(int x){
  30.     return lower_bound(b+1,b+1+m,x)-b;
  31. }
  33. inline int bk(int x){
  34.     return b[x];
  35. } 
  37. inline int rank(int x){
  38.     return sa(x-1)+1;
  39. }
  41. inline int kth(int x){
  42.     int l=1,r=m;
  43.     while(l<r){
  44.         if(sa(mid)<x) l=mid+1;
  45.         else r=mid;
  46.     }
  47.     return bk(l);
  48. }
  50. void fre(){
  51.     freopen("tree.in","r",stdin);
  52.     freopen("my.out","w",stdout);
  53. }
  55. inline int dsa(int x){
  56.     return sa(x)-sa(x-1);
  57. }
  59. int main(){
  60. //  fre();
  61.     scanf("%d",&n);
  62.     for(int i=1;i<=n;i++){
  63.         scanf("%d%d",&opt[i],&a[i]);
  64.         if(opt[i]^4) b[++cnt]=a[i];
  65.     }
  66.     sort(b+1,b+1+cnt);
  67.     m=unique(b+1,b+1+cnt)-b-1;
  68.     for(int i=1;i<=n;i++){
  69.         if(opt[i]==1) add(gt(a[i]),1);
  70.         if(opt[i]==2) add(gt(a[i]),-1);
  71.         if(opt[i]==3) printf("%d\n",rank(gt(a[i])));
  72.         if(opt[i]==4) printf("%d\n",kth(a[i]));
  73.         if(opt[i]==5) printf("%d\n",kth(rank(gt(a[i]))-1));
  74.         if(opt[i]==6) printf("%d\n",kth(rank(gt(a[i]))+dsa(gt(a[i]))));
  76.     }
  77. }

还有vector[虽然最坏情况被卡炸，但是娱乐一下么~]

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int n;
  6. vector<int> v;
  8. int main(){
  9.     scanf("%d",&n);
  10.     for(int i=1;i<=n;i++){
  11.         int opt,x;
  12.         scanf("%d%d",&opt,&x);
  13.         if(opt==1) v.insert(lower_bound(v.begin(),v.end(),x),x);
  14.         if(opt==2) v.erase(lower_bound(v.begin(),v.end(),x));
  15.         if(opt==3) printf("%d\n",lower_bound(v.begin(),v.end(),x)-v.begin()+1);
  16.         if(opt==4) printf("%d\n",v[x-1]);
  17.         if(opt==5) printf("%d\n",*--lower_bound(v.begin(),v.end(),x));
  18.         if(opt==6) printf("%d\n",*upper_bound(v.begin(),v.end(),x));
  19.     }
  20. }

题目：

Luogu 2596[ZJOI2006]书架

这里Splay维护的是在Shelf上面的位置。
其实就是维护一段序列，top和bottom就相当于把左（右）子树全都拎走，
Pos记录每个值对应点的编号（Splay不是按照编号排序，按位置排序）。
Insert操作就是和前驱（后继）交换信息
Ask和Query就是常规操作了

  1.   #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N=1e5+7;
  6. int siz[N],son[N][2],f[N],w[N],pos[N],n,m,rt,tot;
  7. char ch[50];
  9. int inline read()
  10. {
  11.     int x=0,f=1;char ch=getchar();
  12.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  14.     return x*f;
  15. }
  17. inline void update(int x){
  18. siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
  19. }
  21. inline void rotate(int x){
  22.     int y=f[x],z=f[y],t=son[y][0]==x;
  23.     if(z) son[z][y==son[z][1]]=x;
  24.     f[x]=z;
  25.     son[y][!t]=son[x][t];
  26.     f[son[x][t]]=y;
  27.     son[x][t]=y;
  28.     f[y]=x;
  29.     update(y);
  30.     update(x);
  31. }
  33. inline void splay(int x,int s){
  34.     if(s==0) rt=x;
  35.     while(f[x]!=s) {
  36.         int y=f[x],z=f[y];
  37.         if(z!=s) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
  38.         rotate(x);
  39.     }
  40. }
  42. inline void insert(int x){
  43.     w[++tot]=x;
  44.     siz[tot]=1;
  45.     son[tot][0]=son[tot][1]=0;
  46.     pos[x]=tot;
  47.     if(tot>1){
  48.         son[tot-1][1]=tot;
  49.         f[tot]=tot-1;
  50.         splay(tot,0);
  51.     }
  52. }
  54. inline int find(int x){
  55.     int s=rt;
  56.     while(1){
  57.         if(siz[son[s][0]]+1==x) return s;
  58.         if(siz[son[s][0]]>=x) s=son[s][0];
  59.         else if(siz[son[s][0]]+1<x) x-=siz[son[s][0]]+1,s=son[s][1];
  60.     }
  61.     return 0;
  62. }
  64. inline void top(int x){
  65.     x=pos[x];
  66.     splay(x,0);
  67.     if(!son[x][0]) return;
  68.     if(!son[x][1]) son[x][1]=son[x][0],son[x][0]=0;
  69.     else{
  70.         int y=find(siz[son[x][0]]+2);
  71.         f[son[x][0]]=y;
  72.         son[y][0]=son[x][0];
  73.         son[x][0]=0;
  74.         splay(y,0);
  75.     }
  76. }
  78. inline void bottom(int x){
  79.     x=pos[x];
  80.     splay(x,0);
  81.     if(!son[x][1]) return;
  82.     if(!son[x][0]) son[x][0]=son[x][1],son[x][1]=0;
  83.     else{
  84.         int y=find(siz[son[x][0]]);
  85.         f[son[x][1]]=y;
  86.         son[y][1]=son[x][1];
  87.         son[x][1]=0;
  88.         splay(y,0);
  89.     }
  90. }
  92. /*void ins(int f,int x)
  93. {
  94.     if (!f) return;
  95.     splay(pos[x],0);
  96.     int y=find(f==1?siz[son[pos[x]][0]]+2:siz[son[pos[x]][0]]);
  97.     int x1=w[y],x2=pos[x];
  98.     swap(pos[x],pos[x1]);
  99.     swap(w[x2],w[y]);
  100. }*/
  102. inline void ins(int f,int x){
  103.     if(!f) return;
  104.     splay(pos[x],0);
  105.     int s;
  106.     if(f==1){//suf
  107.        s=find(siz[son[pos[x]][0]]+2);
  108.        int t=pos[x],ff=w[s];
  109.        swap(pos[x],pos[ff]);
  110.        swap(w[t],w[s]);
  111.     }
  112.     else{
  113.        s=find(siz[son[pos[x]][0]]);
  114.        int t=pos[x],ff=w[s];
  115.        swap(pos[x],pos[ff]);
  116.        swap(w[t],w[s]);
  117.     }
  118. }
  120. inline void getans(int x){
  121.     splay(pos[x],0);
  122.     printf("%d\n",siz[son[pos[x]][0]]);
  123. }
  125. int main(){
  126. //  freopen("tx.txt","r",stdin);
  127.     scanf("%d%d",&n,&m);
  128.     rt=1;
  129.     for(int i=1;i<=n;i++){
  130.         int p;
  131.         scanf("%d",&p);
  132.         insert(p);
  133.     }
  134.     for(int i=1;i<=m;i++){
  135.         scanf("%s",ch);
  136.         switch(ch[0])
  137.         {
  138.             case 'T':top(read());break;
  139.             case 'B':bottom(read());break;
  140.             case 'I':ins(read(),read());break;
  141.             case 'A':getans(read());break;
  142.             case 'Q':printf("%d\n",w[find(read())]);break;
  143.         }
  144.     }
  145. }

Luogu P2042 [NOI2005]维护数列

这道题真的太恶心了
首先空间不够，要开队列recycle
其次就是在区间翻转的时候，lx和rx也要交换位置
最后就是在find的时候需要pushdown(因为这个调了一下午(>_<)！！)

节点要维护区间和，前后缀

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N=1e6+7;
  5. const int inf=0x7ffffff;
  7. int n,m,rt,cnt;
  8. int f[N],son[N][2],w[N],siz[N],id[N],lx[N],rx[N],mx[N],sum[N],a[N];
  9. bool tag[N],rev[N];
  11. queue<int> q;
  13. inline void update(int x){
  14.     int l=son[x][0],r=son[x][1];
  15.     sum[x]=sum[l]+sum[r]+w[x];
  16.     siz[x]=siz[l]+siz[r]+1;
  17.     mx[x]=max(mx[l],max(mx[r],rx[l]+w[x]+lx[r]));
  18.     lx[x]=max(lx[l],sum[l]+w[x]+lx[r]);
  19.     rx[x]=max(rx[r],sum[r]+w[x]+rx[l]);
  20. } 
  22. inline void pushdown(int x){
  23.     int l=son[x][0],r=son[x][1];
  24.     if(tag[x]){
  25.         rev[x]=tag[x]=0;
  26.         if(l) tag[l]=1,w[l]=w[x],sum[l]=w[x]*siz[l];
  27.         if(r) tag[r]=1,w[r]=w[x],sum[r]=w[x]*siz[r];
  28.         if (w[x]>=0){
  29.             if (l)lx[l]=rx[l]=mx[l]=sum[l];
  30.             if (r)lx[r]=rx[r]=mx[r]=sum[r];
  31.         }else{
  32.             if (l)lx[l]=rx[l]=0,mx[l]=w[x];
  33.             if (r)lx[r]=rx[r]=0,mx[r]=w[x];
  34.         }
  35.     }
  36.     if(rev[x]){
  37.         rev[x]=0;rev[l]^=1;rev[r]^=1;
  38.         swap(lx[l],rx[l]);swap(lx[r],rx[r]);
  39.         swap(son[l][0],son[l][1]);swap(son[r][0],son[r][1]);
  40.     }
  41. }
  43. inline void rotate(int x){
  44.     int y=f[x],z=f[y],t=son[y][0]==x;
  45.     if(z) son[z][son[z][1]==y]=x;f[x]=z;
  46. //    if (y==k)k=x;else son[z][son[z][1]==y]=x;
  47.     son[y][!t]=son[x][t];f[son[x][t]]=y;
  48.     son[x][t]=y;f[y]=x;
  49.     update(y);
  50.     update(x);
  51. }
  53. inline void splay(int x,int s){
  54.     while(f[x]!=s){
  55.         int y=f[x],z=f[y];
  56.         if(z!=s) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
  57.         rotate(x);
  58.     }
  59.     if(!s) rt=x;
  60. }
  62. inline int find(int x){
  63.     int s=rt;
  64.     while(1){
  65.         pushdown(s);
  66.         if(siz[son[s][0]]+1==x) return s;
  67.         if(siz[son[s][0]]>=x) s=son[s][0];
  68.         else x-=siz[son[s][0]]+1,s=son[s][1];
  69.     }
  70. }
  72. /*inline void rotate(int x,int &k){
  73.     int y=f[x],z=f[y],l=(son[y][1]==x),r=l^1;
  74.     if (y==k)k=x;else son[z][son[z][1]==y]=x;
  75.     f[son[x][r]]=y;f[y]=x;f[x]=z;
  76.     son[y][l]=son[x][r];son[x][r]=y;
  77.     update(y);
  78.     update(x);
  79. }
  80. inline void splay(int x,int &k){
  81.     while (x!=k){
  82.         int y=f[x],z=f[y];
  83.         if (y!=k){
  84.             if (son[z][0]==y ^ son[y][0]==x)rotate(x,k);
  85.                 else rotate(y,k);
  86.         }
  87.         rotate(x,k);
  88.     }
  89. }
  91. inline int find(int x){
  92.     int s=rt;
  93.     while(1){
  94.         pushdown(s);
  95.         if(siz[son[s][0]]+1==x) return s;
  96.         if(siz[son[s][0]]>=x) s=son[s][0];
  97.         else x-=siz[son[s][0]]+1,s=son[s][1];
  98. }
  99. }*/
  101. inline void recycle(int x){
  102.     int &l=son[x][0],&r=son[x][1];
  103.     if(l) recycle(l);
  104.     if(r) recycle(r);
  105.     q.push(x);
  106.     f[x]=l=r=tag[x]=rev[x]=0;
  107. }
  109. inline int split(int k,int tot){
  110.     int x=find(k),y=find(k+tot+1);
  111.     splay(x,0);
  112.     splay(y,x);
  113.     return son[y][0];
  114. }
  116. inline void sa(int k,int tot){
  117.     int x=split(k,tot);
  118.     printf("%d\n",sum[x]);
  119. }
  121. inline void modify(int k,int tot,int val){
  122.     int x=split(k,tot),y=f[x];
  123.     w[x]=val;
  124.     tag[x]=1;
  125.     sum[x]=siz[x]*val;
  126.     if (val>=0)lx[x]=rx[x]=mx[x]=sum[x];
  127.     else lx[x]=rx[x]=0,mx[x]=val;
  128.     update(y);
  129.     update(f[y]);
  130. }
  132. inline void rever(int k,int tot){
  133.     int x=split(k,tot),y=f[x];
  134.     if (!tag[x]){
  135.         rev[x]^=1;
  136.         swap(son[x][0],son[x][1]);
  137.         swap(lx[x],rx[x]);
  138.         update(y);update(f[y]);
  139.     }
  140. }
  142. inline void del(int k,int tot){
  143.     int x=split(k,tot),y=f[x];
  144.     recycle(x);
  145.     son[y][0]=0;
  146.     update(y);update(f[y]);
  147. }
  149. inline void build(int l,int r,int fa){
  150.     int mid=(l+r)>>1,now=id[mid],pre=id[fa];
  151.     if(l==r) {
  152.         mx[now]=sum[now]=a[l];
  153.         tag[now]=rev[now]=0;
  154.         lx[now]=rx[now]=max(a[l],0);
  155.         siz[now]=1;
  156.     }
  157.     if(l<mid) build(l,mid-1,mid);
  158.     if(r>mid) build(mid+1,r,mid);
  159.     w[now]=a[mid];
  160.     f[now]=pre;
  161.     update(now);
  162.     son[pre][mid>=fa]=now;
  163. }
  165. inline void insert(int k,int tot){
  166.     for(int i=1;i<=tot;i++) scanf("%d",&a[i]);
  167.     for(int i=1;i<=tot;i++){
  168.         if (!q.empty())id[i]=q.front(),q.pop();
  169.         else id[i]=++cnt;//利用队列中记录的冗余节点编号
  170.     }
  171.     build(1,tot,0);
  172.     int z=id[(1+tot)>>1];
  173.     int x=find(k+1),y=find(k+2);
  174.     splay(x,0);
  175.     splay(y,x);
  176.     f[z]=y;
  177.     son[y][0]=z;
  178.     update(y);
  179.     update(x);
  180. }
  182. inline int read(){
  183.     int x=0,ff=1;char ch=getchar();
  184.     while (ch<'0' || ch>'9'){if (ch=='-')ff=-1;ch=getchar();}
  185.     while ('0'<=ch && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  186.     return x*ff;
  187. }
  189. int main(){
  190.     scanf("%d%d",&n,&m);
  191.      mx[0]=a[1]=a[n+2]=-inf;
  192.      for(int i=1;i<=n;i++){
  193.         scanf("%d",&a[i+1]);
  194.      }
  195.      for(int i=1;i<=n+2;i++) id[i]=i;
  196.      build(1,n+2,0);
  197.      rt=(n+3)>>1;
  198.      cnt=n+2;
  199.      int k,tot,val;
  200.      char ch[20];
  201.      while(m--){
  202.         scanf("%s",ch);
  203.         if (ch[0]!='M' || ch[2]!='X') k=read(),tot=read();
  204.         if (ch[0]=='I')insert(k,tot);
  205.         if (ch[0]=='D')del(k,tot);
  206.         if (ch[0]=='M'){
  207.             if (ch[2]=='X')printf("%d\n",mx[rt]);
  208.             else val=read(),modify(k,tot,val);
  209.         }
  210.         if (ch[0]=='R')rever(k,tot);
  211.         if (ch[0]=='G')sa(k,tot);
  212.      }
  213. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注