HDU_3487

    拿这个题目练了一下splay的区间的切割，也就是删除、移动、添加一个连续的区间。

#include
     
       #include
      
        #define MAXD 300010 int N, M, T, node, size[MAXD], rev[MAXD], left[MAXD], right[MAXD], pre[MAXD], key[MAXD], ans[MAXD], P; void newnode(int &cur, int k) {
       cur = ++ node;     key[cur] = k;     size[cur] = 1;     rev[cur] = 0;     left[cur] = right[cur] = 0; } void update(int cur) {
       size[cur] = size[left[cur]] + size[right[cur]] + 1; } void pushdown(int cur) {
   if(rev[cur])     {
   int ls = left[cur], rs = right[cur];         rev[ls] = (rev[ls] + 1) & 1, rev[rs] = (rev[rs] + 1) & 1;         left[cur] = rs, right[cur] = ls;         rev[cur] = 0;     } } void build(int &cur, int x, int y, int p) {
   int mid = (x + y) / 2;     newnode(cur, mid);     pre[cur] = p; if(x == y) return ; if(x < mid)         build(left[cur], x, mid - 1, cur); if(mid < y)         build(right[cur], mid + 1, y, cur);     update(cur); } void init() {
       T = node = size[0] = left[0] = right[0] = 0;     newnode(T, 0), newnode(right[T], N + 1);     size[T] = 2, pre[T] = 0, pre[right[T]] = T;     build(left[right[T]], 1, N, right[T]);     update(right[T]), update(T); } void leftrotate(int x) {
   int y = right[x], p = pre[x];     right[x] = left[y]; if(right[x])         pre[right[x]] = x;     left[y] = x;     pre[x] = y;     pre[y] = p; if(p == 0)         T = y; else         right[p] == x ? right[p] = y : left[p] = y;     update(x); } void rightrotate(int x) {
   int y = left[x], p = pre[x];     left[x] = right[y]; if(left[x])         pre[left[x]] = x;     right[y] = x;     pre[x] = y;     pre[y] = p; if(p == 0)         T = y; else         right[p] == x ? right[p] = y : left[p] = y;     update(x); } void splay(int x, int goal) {
   int y, z; for(;;)     {
   if((y = pre[x]) == goal) break; if((z = pre[y]) == goal)             right[y] == x ? leftrotate(y) : rightrotate(y); else         {
   if(right[z] == y)             {
   if(right[y] == x)                     leftrotate(z), leftrotate(y); else                     rightrotate(y), leftrotate(z);             } else             {
   if(left[y] == x)                     rightrotate(z), rightrotate(y); else                     leftrotate(y), rightrotate(z);             }         }     }     update(x); } void rotateto(int k, int goal) {
   int i = T; for(;;)     {
           pushdown(i); if(k == size[left[i]] + 1) break; if(k <= size[left[i]])             i = left[i]; else             k -= size[left[i]] + 1, i = right[i];     }     splay(i, goal); } void cut(int x, int y, int z) {
   int k, t;     rotateto(x, 0), rotateto(y + 2, T);     t = left[right[T]];     left[right[T]] = 0;     update(right[T]), update(T);     rotateto(z + 1, 0), rotateto(z + 2, T);     pre[t] = right[T];     left[right[T]] = t;     update(right[T]), update(T); } void flip(int x, int y) {
   int k;     rotateto(x, 0), rotateto(y + 2, T);     k = left[right[T]];     rev[k] = (rev[k] + 1) & 1; } void solve() {
   int i, x, y, z; char b[10]; for(i = 0; i < M; i ++)     {
           scanf("%s", b); if(b[0] == 'C')         {
               scanf("%d%d%d", &x, &y, &z);             cut(x, y, z);         } else         {
               scanf("%d%d", &x, &y);             flip(x, y);         }     } } void dfs(int cur) {
       pushdown(cur); if(left[cur])         dfs(left[cur]);     ans[P ++] = key[cur]; if(right[cur])         dfs(right[cur]); } void printresult() {
   int i;     P = 0;     dfs(T);     printf("%d", ans[1]); for(i = 2; i < P - 1; i ++)         printf(" %d", ans[i]);     printf("\n"); } int main() {
   while(scanf("%d%d", &N, &M) == 2)     {
   if(N < 0 && M < 0) break;         init();         solve();         printresult();     } return 0; }