阅读见https://www.zybuluo.com/ysner/note/1053583

普通平衡树

得了，平衡树的基本操作我怎么会自己写呢？详见

文艺平衡树

功能：序列反转

原理：将区间[l,r]的端点l-1,和r+1不断的通过伸展操作即splay到根，将l-1伸展到根，将r+1伸展到根的右儿子，那么[l,r]这段区间就在根的右儿子的左儿子上了。

实现：把序列右端点转到Splay左端点上面，同时打个懒标记，到时候（kth和write）转即可。

注意：1.两个边界节点1和n+2防死循环

2.注意到数的位置与它的大小没什么关系，我们应维护的是数的位置而非一般而言的权值。

3.可以给每个节点打一个懒标记mk，若要转两次就抵消。

4.每个点唯一。

5.中序遍历输出。

1. 1. #include<iostream>
   2. #include<cstdio>
   3. #include<cstdlib>
   4. #include<cstring>
   5. #include<cmath>
   6. #include<algorithm>
   7. #define ll long long
   8. #define re register
   9. #define il inline
   10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
   11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
   12. using namespace std;
   13. const int N=2e5+100;
   14. int n,m,k,root,tot;
   15. il int gi()
   16. {
   17. re int x=0,t=1;
   18. re char ch=getchar();
   19. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   20. if(ch=='-') t=-1,ch=getchar();
   21. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   22. return x*t;
   23. }
   24. struct node
   25. {
   26. int z[2],fa,w,sz,mk;
   27. }t[N];
   28. il void pushup(re int x)
   29. {
   30. t[x].sz=t[t[x].z[0]].sz+t[t[x].z[1]].sz+1;
   31. }
   32. il void pushdown(re int x)
   33. {
   34. if(t[x].mk)
   35. {
   36. t[t[x].z[0]].mk^=1;
   37. t[t[x].z[1]].mk^=1;
   38. t[x].mk=0;
   39. swap(t[x].z[0],t[x].z[1]);
   40. }
   41. }
   42. il void rotate(re int x)
   43. {
   44. re int y=t[x].fa,z=t[y].fa,k=t[y].z[1]==x;
   45. t[z].z[t[z].z[1]==y]=x;//x到y的位置
   46. t[x].fa=z;
   47. t[y].z[k]=t[x].z[k^1];//y的儿子变为x的相对儿子
   48. t[t[x].z[k^1]].fa=y;
   49. t[x].z[k^1]=y;//x的相对儿子变为y
   50. t[y].fa=x;
   51. pushup(y);pushup(x);
   52. }
   53. il void Splay(re int x,re int tar)
   54. {
   55. while(t[x].fa!=tar)
   56. {
   57. re int y=t[x].fa,z=t[y].fa;
   58. if(z!=tar) (t[z].z[1]==y)^(t[y].z[1]==x)?rotate(x):rotate(y);
   59. rotate(x);
   60. }
   61. if(!tar) root=x;
   62. }
   63. il void insert(re int x)
   64. {
   65. re int u=root,fa=0;
   66. while(u&&t[u].w!=x) fa=u,u=t[u].z[x>t[u].w];
   67. u=++tot;
   68. if(fa) t[fa].z[x>t[fa].w]=u;
   69. t[tot].z[0]=t[tot].z[1]=0;
   70. t[tot].sz=1;
   71. t[tot].w=x;t[tot].fa=fa;
   72. Splay(u,0);
   73. }
   74. il int kth(re int k)
   75. {
   76. re int u=root;
   77. while(233)
   78. {
   79. pushdown(u);
   80. if(t[t[u].z[0]].sz>=k) u=t[u].z[0];
   81. else if(t[t[u].z[0]].sz+1==k) return u;
   82. else k-=t[t[u].z[0]].sz+1,u=t[u].z[1];//由于为编号排序，每个点唯一
   83. }
   84. }
   85. il void work(re int l,re int r)
   86. {
   87. l=kth(l);r=kth(r+2);
   88. Splay(l,0);Splay(r,l);
   89. t[t[t[root].z[1]].z[0]].mk^=1;//mk的本质是一种懒标记，若要转两次就抵消???
   90. }
   91. il void write(re int x)
   92. {
   93. pushdown(x);
   94. if(t[x].z[0]) write(t[x].z[0]);
   95. if(t[x].w>1&&t[x].w<n+2) printf("%d ",t[x].w-1);
   96. if(t[x].z[1]) write(t[x].z[1]);//中序遍历
   97. }
   98. int main()
   99. {
   100. n=gi();m=gi();
   101. fp(i,1,n+2) insert(i);//1和n+2是空的边界，防止死循环
   102. while(m--)
   103. {
   104. re int l=gi(),r=gi();
   105. work(l,r);
   106. }
   107. write(root);printf("\n");
   108. return 0;
   109. }