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

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. }
  9. inline int pre(int x){
  10. find(x);
  11. int s=rt;
  12. if(w[s]<x) return s;
  13. s=son[s][0];
  14. while(son[s][1]) s=son[s][1];
  15. return s;
  16. }

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

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

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

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

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

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

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

题目:

Luogu 2596[ZJOI2006]书架

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

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

Luogu P2042 [NOI2005]维护数列

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

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

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