P3391 【模板】文艺平衡树

admin

https://www.luogu.com.cn/problem/P3391

题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 5 4 3 2 1，翻转区间是 [2,4] 的话，结果是 5 2 3 4 1。

输入格式
第一行两个正整数 n,m，表示序列长度与操作个数。序列中第 i 项初始为 i。
接下来 m 行，每行两个正整数 l,r，表示翻转的区间。

输出格式
输出一行 n 个正整数，表示原始序列经过 m 次变换后的结果。

输入输出样例
输入 #1复制
5 3
1 3
1 3
1 4
输出 #1复制
4 3 2 1 5
说明/提示
【数据范围】
对于100% 的数据，1≤n,m≤100000，1≤l≤r≤n。

admin

简易SPLAY裸体，作为SPLAY的入门很好！

admin

SPLAY用于序列操作的
一般加上首尾两个假节点，这样旋转时候

admin

SPLAY用于序列操作的
一般加上首尾两个假节点，这样旋转时候

admin

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=0X3FFFFFFF;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,fa,s[2],sz,rev;
   
8. } a[N];
   
9. int n, tot, root;
   
10. void ArrayPr()   
    
11. {
    
12.         cout<<endl<<"  i ";
    
13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
14.         cout<<endl<<"val ";
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
16.         cout<<endl<<" s0 ";
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
18.         cout<<endl<<" s1 ";
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
20.         cout<<endl<<" fa ";
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
    
22.         cout<<endl<<" sz ";
    
23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
24.         cout<<endl<<"rev ";
    
25.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rev;
    
26.         cout<<endl;
    
27. }
    
28. void pushdown(int rt)
    
29. {
    
30.         if (rt==0) return ;
    
31.         int R=a[rt].rev;
    
32.         int l=a[rt].s[0], r=a[rt].s[1];
    
33.         if (R>0)  
    
34.                 {
    
35.                         a[rt].s[0]=r,a[rt].s[1]=l;
    
36.                         a[rt].rev=0;
    
37.                         if (l>0)a[l].rev^=1;
    
38.                         if (r>0)a[r].rev^=1;
    
39.                 }
    
40. }
    
41. void pushup(int rt)
    
42. {
    
43.         int l=a[rt].s[0], r=a[rt].s[1];
    
44.         a[rt].sz=a[l].sz+a[r].sz+1;
    
45. }
    
46. void BSTPr(int rt)   
    
47. {
    
48.         if (rt>0)
    
49.                 {
    
50.                         BSTPr(a[rt].s[0]);
    
51.                         cout<<a[rt].val<<' ';
    
52.                         BSTPr(a[rt].s[1]);
    
53.                 }
    
54. }
    
55. int Son(int x)
    
56. {
    
57.         int y=a[x].fa;
    
58.         return  a[y].s[1]==x;
    
59. }
    
60. void R(int x)
    
61. {
    
62.         int y=a[x].fa;
    
63.         int z=a[y].fa;
    
64.         pushdown(y),pushdown(x);///下传
    
65.         int k=Son(x);
    
66.         int v=a[x].s[k^1];
    
67. 
    
68.         a[y].s[k]=v,a[v].fa=y;///v挂在y下
    
69.         a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
    
70.         a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
    
71.         pushup(y),pushup(x);///上传
    
72. }
    
73. inline void Splay(int x,int rt=root)  
    
74. {
    
75.         rt=a[rt].fa;
    
76.         int y,z;
    
77. 
    
78.         while(a[x].fa!=rt)  
    
79.                 {
    
80.                         y=a[x].fa,z=a[y].fa;;
    
81.                         if(z!=rt)
    
82.                                 if(Son(x)==Son(y))R(y);
    
83.                                 else R(x);
    
84.                         R(x);
    
85.                 }
    
86.         if(rt==0)root=x;
    
87. }
    
88. int Getkth(int rt,int k) ///第k个的数的位置
    
89. {
    
90.         pushdown(rt);
    
91.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
    
92.         if(l+1==k) return rt;
    
93.         if(l+1>k) return Getkth(a[rt].s[0], k); ///左儿子里去找
    
94.         if(l+1<k) return Getkth(a[rt].s[1], k-(l+1));
    
95. }
    
96. int Build(int l,int r)
    
97. {
    
98.         if (l>r) return 0;
    
99.         if (l==r)
    
100.                 {
     
101.                         a[l].val=l-1;
     
102.                         a[l].sz=1;
     
103.                         return  l;
     
104.                 }
     
105.         int m=(l+r)/2;
     
106.         int L=a[m].s[0]=Build(l,m-1);
     
107.         int R=a[m].s[1]=Build(m+1,r);
     
108.         a[m].sz=r-l+1;
     
109.         a[m].val=m-1;
     
110.         a[L].fa=a[R].fa=m;
     
111.         return m;
     
112. }
     
113. void Get(int x,int y) ///把 第x个转到根，y转到x的右子树
     
114. {
     
115.         int l=Getkth(root,x);
     
116.         int r=Getkth(root,y);
     
117.         Splay(l,root);
     
118.         Splay(r,a[root].s[1]);
     
119. }
     
120. int main()
     
121. {
     
122.         int m,x,opt,L,R,V;
     
123.         cin>>n>>m;
     
124. ///初始建树
     
125.         tot=n+2;
     
126.         root=Build(1,tot);
     
127.         while(m--)
     
128.                 {
     
129.                         cin>>L>>R;
     
130.                         Get(L,R+2);
     
131.                         int t=a[root].s[1];
     
132.                         t=a[t].s[0];
     
133.                         a[t].rev^=1;
     
134.                 }
     
135.         Get(1,n+2);
     
136.         int t=a[root].s[1];
     
137.         t=a[t].s[0];
     
138.         BSTPr(t);
     
139.         return 0;
     
140. }
     
141. /*
     
142. 5 3
     
143. 1 3
     
144. 1 3
     
145. 1 4
     
146. */
     

复制代码

admin

DZY同学提醒：我的那个BSTPr里面少写了一句pushdown(rt)！