HDU-3487 Play with Chain Splay tee区間反転、移動
35453 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3487
1つの数列に対して2つの操作があります:1.CUT a b c、まずa-b区間の数を取り出して、それからそれらを取り出した後のc番目の数の後ろに置きます.2.FLIP a bは、区間a-bの数を反転させる.1つ目の操作については,2回の区間移動を行い,a−1番目の数Splayからルートノード,b+1番目の数Splayからrootの右の息子,ch[ch[root][1]][0]はその区間を表し,その後それらを除去し,移動区間でc番目の数Splayからroot,c+1番目の数Splayからrootの右の息子,さらに先ほどの区間を加算すればよい.2回目の操作はノードごとに価格を設定し、息子が反転しているかどうかを示し、怠惰な操作マークで更新を遅らせます.の
1つの数列に対して2つの操作があります:1.CUT a b c、まずa-b区間の数を取り出して、それからそれらを取り出した後のc番目の数の後ろに置きます.2.FLIP a bは、区間a-bの数を反転させる.1つ目の操作については,2回の区間移動を行い,a−1番目の数Splayからルートノード,b+1番目の数Splayからrootの右の息子,ch[ch[root][1]][0]はその区間を表し,その後それらを除去し,移動区間でc番目の数Splayからroot,c+1番目の数Splayからrootの右の息子,さらに先ほどの区間を加算すればよい.2回目の操作はノードごとに価格を設定し、息子が反転しているかどうかを示し、怠惰な操作マークで更新を遅らせます.の
1 //STATUS:C++_AC_578MS_6452KB
2 #include <functional>
3 #include <algorithm>
4 #include <iostream>
5 //#include <ext/rope>
6 #include <fstream>
7 #include <sstream>
8 #include <iomanip>
9 #include <numeric>
10 #include <cstring>
11 #include <cassert>
12 #include <cstdio>
13 #include <string>
14 #include <vector>
15 #include <bitset>
16 #include <queue>
17 #include <stack>
18 #include <cmath>
19 #include <ctime>
20 #include <list>
21 #include <set>
22 #include <map>
23 using namespace std;
24 //using namespace __gnu_cxx;
25 //define
26 #define pii pair<int,int>
27 #define mem(a,b) memset(a,b,sizeof(a))
28 #define lson l,mid,rt<<1
29 #define rson mid+1,r,rt<<1|1
30 #define PI acos(-1.0)
31 //typedef
32 typedef __int64 LL;
33 typedef unsigned __int64 ULL;
34 //const
35 const int N=300010;
36 const int INF=0x3f3f3f3f;
37 const int MOD=100000,STA=8000010;
38 const LL LNF=1LL<<60;
39 const double EPS=1e-8;
40 const double OO=1e15;
41 const int dx[4]={-1,0,1,0};
42 const int dy[4]={0,1,0,-1};
43 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
44 //Daily Use ...
45 inline int sign(double x){return (x>EPS)-(x<-EPS);}
46 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
47 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
48 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
49 template<class T> inline T Min(T a,T b){return a<b?a:b;}
50 template<class T> inline T Max(T a,T b){return a>b?a:b;}
51 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
52 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
53 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
54 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
55 //End
56
57 #define Key_value ch[ch[root][1]][0]
58 int pre[N],ch[N][2]; // ， ， (0 ，1 ), ，
59 int sz[N],st[N]; // ，
60 int root,tot,top; // ， ，
61 //
62 int key[N];
63 bool rev[N];
64 int n,m;
65 //debug copy from hh
66 void Treaval(int x) {
67 if(x) {
68 Treaval(ch[x][0]);
69 printf(" %2d: %2d %2d %2d size = %2d rev = %2d key = %2d
",x,ch[x][0],ch[x][1],pre[x],sz[x],rev[x],key[x]);
70 Treaval(ch[x][1]);
71 }
72 }
73 void debug() {printf("%d
",root);Treaval(root);}
74 // Debug
75 //
76 void NewNode(int &x,int fa,int k)
77 {
78 if(top)x=st[--top];
79 else x=++tot;
80 key[x]=k;
81 pre[x]=fa;
82 sz[x]=1;
83 rev[x]=0;
84 ch[x][0]=ch[x][1]=0; //
85 }
86
87 void Push_Up(int x)
88 {
89 sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
90 }
91
92 void Push_Down(int x)
93 {
94 if(rev[x]){
95 rev[ch[x][0]]^=1;
96 rev[ch[x][1]]^=1;
97 swap(ch[x][0],ch[x][1]);
98 rev[x]=0;
99 }
100 }
101 // ，kind 1 ，kind 0
102 void Rotate(int x,int kind)
103 {
104 int y=pre[x],z=pre[y];
105 Push_Down(y);
106 Push_Down(x); // y ， x
107 // SBT，
108 ch[y][!kind]=ch[x][kind];
109 pre[ch[x][kind]]=y;
110 // ，
111 if(z)ch[z][ch[z][1]==y]=x;
112 pre[x]=z;
113 ch[x][kind]=y;
114 pre[y]=x;
115 Push_Up(y); // y ， x ，x Push_Down， x
116 }
117 //Splay ， r goal
118 void Splay(int x,int goal)
119 {
120 int y,z,kind;
121 while(pre[x]!=goal){
122 // ，goal 0 ，
123 y=pre[x];
124 Push_Down(pre[y]);Push_Down(y);Push_Down(x); // ， ， !!
125 if(pre[y]==goal){
126 Rotate(x,ch[y][0]==x);
127 }
128 else {
129 kind=ch[pre[y]][0]==y;
130 // ，
131 if(ch[y][kind]==x){
132 Rotate(x,!kind);
133 Rotate(x,kind);
134 }
135 // ，
136 else {
137 Rotate(y,kind);
138 Rotate(x,kind);
139 }
140 }
141 }
142 //
143 Push_Up(x);
144 if(goal==0)root=x;
145 }
146
147 void RotateTo(int k,int goal)
148 {
149 int x=root;
150 Push_Down(x);
151 while(sz[ch[x][0]]!=k){
152 if(sz[ch[x][0]]>k)
153 x=ch[x][0];
154 else {
155 k-=sz[ch[x][0]]+1;
156 x=ch[x][1];
157 }
158 Push_Down(x);
159 }
160 Splay(x,goal);
161 }
162 // ， ，
163 void BuildTree(int &x,int l,int r,int fa)
164 {
165 if(l>r)return;
166 int mid=(l+r)>>1;
167 NewNode(x,fa,mid);
168 BuildTree(ch[x][0],l,mid-1,x);
169 BuildTree(ch[x][1],mid+1,r,x);
170 Push_Up(x);
171 }
172
173 void Init()
174 {
175 root=top=tot=0;
176 ch[0][0]=ch[0][1]=sz[0]=pre[0]=rev[0]=0;
177
178 NewNode(root,0,-1);
179 NewNode(ch[root][1],root,-1);
180 BuildTree(Key_value,1,n,ch[root][1]);
181 Push_Up(ch[root][1]);
182 Push_Up(root);
183 }
184
185 int ok;
186 void print(int u)
187 {
188 if(!u)return;
189 Push_Down(u);
190 print(ch[u][0]);
191 if(key[u]>0){
192 if(ok){printf("%d",key[u]);ok=0;}
193 else printf(" %d",key[u]);
194 }
195 print(ch[u][1]);
196 }
197
198 void Cut(int a,int b,int c)
199 {
200 RotateTo(a-1,0);
201 RotateTo(b+1,root);
202 int s=Key_value;
203 Key_value=0;
204 Splay(ch[root][1],0);
205 RotateTo(c,0);
206 RotateTo(c+1,root);
207 Key_value=s;
208 pre[s]=ch[root][1];
209 Splay(Key_value,0);
210 }
211
212 void Flip(int a,int b)
213 {
214 RotateTo(a-1,0);
215 RotateTo(b+1,root);
216 rev[Key_value]^=1;
217 }
218
219 int main()
220 {
221 // freopen("in.txt","r",stdin);
222 int i,j,a,b,c;
223 char s[10];
224 while(~scanf("%d%d",&n,&m) && (n>=0 || m>=0))
225 {
226 if(n==1){
227 printf("1
");
228 continue;
229 }
230 Init();
231 while(m--){
232 scanf("%s",s);
233 if(s[0]=='C'){
234 scanf("%d%d%d",&a,&b,&c);
235 Cut(a,b,c);
236 }
237 else {
238 scanf("%d%d",&a,&b);
239 Flip(a,b);
240 }
241 }
242 ok=1;
243 print(root);
244 putchar('
');
245 }
246 return 0;
247 }