比较模板的splay题
cut操作和reverse操作。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 5 using namespace std; 6 7 #define Key_value ch[ch[root][1] ][0] 8 9 const int maxn = 5e5+10; 10 const int INF = 0x3f3f3f3f; 11 12 int pre[maxn],ch[maxn][2],key[maxn],sz[maxn]; 13 int root,tot1; 14 int rev[maxn],mi[maxn],add[maxn]; 15 int s[maxn],tot2; 16 int a[maxn],cnt; 17 int n,q; 18 19 void Treavel(int x) 20 { 21 if(x) 22 { 23 Treavel(ch[x][0]); 24 printf("结点:%2d: 左儿子 %2d 右儿子 %2d 父结点 %2d key=%2d size= %2d mi=%2d add=%2d ",x,ch[x][0],ch[x][1],pre[x],key[x],sz[x],mi[x],add[x]); 25 Treavel(ch[x][1]); 26 } 27 } 28 void debug() 29 { 30 printf("root:%d ",root); 31 Treavel(root); 32 } 33 // 34 35 void NewNode(int &r,int father,int k) 36 { 37 if(tot2) r = s[tot2--]; 38 else r = ++tot1; 39 pre[r] = father; 40 ch[r][0] = ch[r][1] = 0; 41 key[r] = k; 42 mi[r] = k; 43 rev[r] = add[r] = 0; 44 sz[r] = 1; 45 } 46 47 void Update_add(int r,int c) 48 { 49 if(!r) return ; 50 key[r] += c; 51 mi[r] += c; 52 add[r] += c; 53 } 54 55 void Update_rev(int r) 56 { 57 if(!r) return ; 58 swap(ch[r][0],ch[r][1]); 59 rev[r] ^= 1; 60 } 61 62 void push_up(int r) 63 { 64 int lson = ch[r][0],rson = ch[r][1]; 65 sz[r] = sz[lson] + sz[rson] + 1; 66 mi[r] = min(min(mi[lson],mi[rson]),key[r]); 67 } 68 69 void push_down(int r) 70 { 71 if(rev[r]) 72 { 73 Update_rev(ch[r][0]); 74 Update_rev(ch[r][1]); 75 rev[r] = 0; 76 } 77 if(add[r]) 78 { 79 Update_add(ch[r][0],add[r]); 80 Update_add(ch[r][1],add[r]); 81 add[r] = 0; 82 } 83 } 84 85 void Build(int &x,int l,int r,int father) 86 { 87 if(l>r) return ; 88 int mid = (l+r)>>1; 89 NewNode(x,father,a[mid]); 90 Build(ch[x][0],l,mid-1,x); 91 Build(ch[x][1],mid+1,r,x); 92 push_up(x); 93 } 94 95 void Init() 96 { 97 root = tot1 = tot2 = 0; 98 ch[root][0] = ch[root][1] = sz[root] = pre[root] = 0; 99 rev[root] = key[root] = 0; 100 mi[root] = INF; 101 NewNode(root,0,0); 102 NewNode(ch[root][1],root,0); 103 for(int i=1;i<=n;i++) a[i] = i; 104 Build(Key_value,1,n,ch[root][1]); 105 push_up(ch[root][1]); 106 push_up(root); 107 } 108 void Rotate(int x,int kind) 109 { 110 int y = pre[x]; 111 push_down(y); 112 push_down(x); 113 ch[y][!kind] = ch[x][kind]; 114 pre[ch[x][kind] ] = y; 115 if(pre[y]) 116 ch[pre[y] ][ch[pre[y]][1]==y ] = x; 117 pre[x] = pre[y]; 118 ch[x][kind] = y; 119 pre[y] = x; 120 push_up(y); 121 } 122 void Splay(int r,int goal) 123 { 124 push_down(r); 125 while(pre[r] != goal) 126 { 127 if(pre[pre[r] ] == goal) 128 { 129 push_down(pre[r]); 130 push_down(r); 131 Rotate(r,ch[pre[r]][0] == r); 132 } 133 else 134 { 135 push_down(pre[pre[r] ]); 136 push_down(pre[r]); 137 push_down(r); 138 int y = pre[r]; 139 int kind = ch[pre[y] ][0] == y; 140 if(ch[y][kind] == r) 141 { 142 Rotate(r,!kind); 143 Rotate(r,kind); 144 } 145 else 146 { 147 Rotate(y,kind); 148 Rotate(r,kind); 149 } 150 } 151 push_up(r); 152 if(goal == 0) root = r; 153 } 154 } 155 156 int Get_kth(int r,int k) 157 { 158 push_down(r); 159 int t = sz[ch[r][0] ] + 1; 160 if(t == k) return r; 161 if(t > k) return Get_kth(ch[r][0],k); 162 else return Get_kth(ch[r][1],k-t); 163 } 164 165 void Insert(int pos,int tot) 166 { 167 for(int i=0;i<tot;i++) scanf("%d",&a[i]); 168 Splay(Get_kth(root,pos+1) , 0); 169 Splay(Get_kth(root,pos+2) , root); 170 Build(Key_value,0,tot-1,ch[root][1]); 171 push_up(ch[root][1]); 172 push_up(root); 173 } 174 void erase(int r) 175 { 176 if(!r) return ; 177 s[++tot2] = r; 178 erase(ch[r][0]); 179 erase(ch[r][1]); 180 } 181 void Delete(int pos,int tot) 182 { 183 Splay(Get_kth(root,pos) ,0); 184 Splay(Get_kth(root,pos+tot+1) , root); 185 erase(Key_value); 186 pre[Key_value] = 0; 187 Key_value = 0; 188 push_up(ch[root][1]); 189 push_up(root); 190 } 191 192 void Reverse(int pos,int tot) 193 { 194 Splay(Get_kth(root,pos) , 0); 195 Splay(Get_kth(root,pos+tot+1), root); 196 Update_rev(Key_value); 197 } 198 199 void Add(int pos,int tot,int c) 200 { 201 Splay(Get_kth(root,pos) , 0); 202 Splay(Get_kth(root,pos+tot+1) , root); 203 Update_add(Key_value,c); 204 push_up(ch[root][1]); 205 push_up(root); 206 } 207 208 int Get_min(int pos,int tot) 209 { 210 Splay(Get_kth(root,pos) , 0); 211 Splay(Get_kth(root,pos+tot+1) , root); 212 return mi[Key_value]; 213 } 214 215 void Revolve(int l,int r,int t) 216 { 217 if(!t) return ; 218 int c = r - t; 219 Splay(Get_kth(root,l) , 0); 220 Splay(Get_kth(root,c+2),root); 221 int tmp = Key_value; 222 Key_value = 0; 223 push_up(ch[root][1]); 224 push_up(root); 225 Splay(Get_kth(root,r-c+l) , 0); 226 Splay(Get_kth(root,r-c+l+1) , root); 227 Key_value = tmp; 228 pre[Key_value] = ch[root][1]; 229 push_up(ch[root][1]); 230 push_up(root); 231 } 232 233 void Cut(int pos,int tot,int n_pos) 234 { 235 //printf("%d %d ",Get_kth(root,pos),Get_kth(root,pos+tot+1)); 236 Splay(Get_kth(root,pos) , 0); 237 Splay(Get_kth(root,pos+tot+1) , root); 238 int tmp = Key_value; 239 Key_value = 0; 240 push_up(ch[root][1]); 241 push_up(root); 242 243 Splay(Get_kth(root,n_pos+1) , 0); 244 Splay(Get_kth(root,n_pos+2) , root); 245 Key_value = tmp; 246 pre[Key_value] = ch[root][1]; 247 push_up(ch[root][1]); 248 push_up(root); 249 } 250 251 void InOrder(int r) 252 { 253 if(!r ) return ; 254 push_down(r); 255 InOrder(ch[r][0]); 256 if(key[r]) a[cnt++] = key[r]; 257 InOrder(ch[r][1]); 258 } 259 260 int m; 261 int main() 262 { 263 while(scanf("%d%d",&n,&m)) 264 { 265 if(n == -1) return -1; 266 Init(); 267 //debug(); 268 char op[10]; 269 int x,y,z; 270 for(int i=0;i<m;i++) 271 { 272 scanf("%s",op); 273 if(op[0] == 'F') 274 { 275 scanf("%d%d",&x,&y); 276 Reverse(x,y-x+1); 277 } 278 else if(op[0] == 'C') 279 { 280 scanf("%d%d%d",&x,&y,&z); 281 Cut(x,y-x+1,z); 282 } 283 } 284 cnt = 0; 285 InOrder(root); 286 for(int i=0;i<cnt;i++) 287 { 288 printf("%d%s",a[i],(i==cnt-1) ? "":" "); 289 } 290 printf(" "); 291 } 292 }