UVA11922–Permutation Transformer (伸展树Splay)

题意：m条操作指令，对于指令 a  b 表示取出第a~b个元素，翻转后添加到排列的尾部。

水题卡了一个小时，一直过不了样例。  原来是 dfs输出的时候 忘记向下传递标记了。

 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 const double eps = 1e-;
 const int maxn = ;
 int siz[maxn],pre[maxn],ch[maxn][],rev[maxn],key[maxn];
 int n,m,tot,root;
 void update_rev(int r)
 {
     if (!r)
         return;
     swap(ch[r][],ch[r][]);
     rev[r] ^= ;
 }
 void push_up(int r)
 {
     siz[r] = siz[ch[r][]] + siz[ch[r][]] + ;
 }
 void push_down(int r)
 {
     if (rev[r])
     {
         update_rev(ch[r][]);
         update_rev(ch[r][]);
         rev[r] = ;
     }
 }
 void NewNode(int &r,int father,int k)
 {
     r = ++tot;
     pre[r] = father;
     ch[r][] = ch[r][] = ;
     key[r] = k;
     rev[r] = ;
     siz[r] = ;
 }
 void build(int &x,int l,int r,int father)
 {
     if (l > r)
         return;
     int mid = (l + r) >> ;
     NewNode(x,father,mid);
     build(ch[x][],l,mid-,x);
     build(ch[x][],mid+,r,x);
     push_up(x);
 }
 void init()
 {
     root = tot = ;
     NewNode(root,,-);
     NewNode(ch[root][],root,-);
     build(ch[ch[root][]][],,n,ch[root][]);
     push_up(root);
     push_up(ch[root][]);
 }
 void Rotate(int x,int kind)
 {
     int y = pre[x];
     push_down(y);
     push_down(x);
     ch[y][!kind] = ch[x][kind];
     pre[ch[x][kind]] = y;
     if (pre[y])
         ch[pre[y]][ch[pre[y]][] == y] = x;
     pre[x] = pre[y];
     ch[x][kind] = y;
     pre[y] = x;
     push_up(y);
 }
 void Splay(int r,int goal)
 {
     push_down(r);
     while (pre[r] != goal)
     {
         if (pre[pre[r]] == goal)
         {
             push_down(pre[r]);
             push_down(r);
             Rotate(r,ch[pre[r]][] == r);
         }
         else
         {
             int y = pre[r];
             int kind = (ch[pre[y]][] == y);
             push_down(pre[y]);
             push_down(y);
             push_down(r);
             if (ch[y][kind] == r)
             {
                 Rotate(y,!kind);
                 Rotate(r,!kind);
             }
             else
             {
                 Rotate(r,kind);
                 Rotate(r,!kind);
             }
         }
     }
     push_up(r);
     if (goal == )
         root = r;
 }
 int Get_kth(int r,int k)
 {
     push_down(r);
     int t = siz[ch[r][]] + ;
     if (k == t)
         return r;
     if (k >= t)
         return Get_kth(ch[r][],k-t);
     else
         return Get_kth(ch[r][],k);
 }
 void Reverse(int u,int v)
 {
     Splay(Get_kth(root,u),);
     Splay(Get_kth(root,v+),root);
     update_rev(ch[ch[root][]][]);
     push_up(ch[root][]);
     push_up(root);
 }
 void dfs(int r)
 {
     if (!r)
         return;
     push_down(r);
     dfs(ch[r][]);
     if (r != - && key[r] != -)        //-1设置的虚节点
         printf("%d\n",key[r]);
     dfs(ch[r][]);
 }
 int main(void)
 {
     #ifndef ONLINE_JUDGE
         freopen("in.txt","r",stdin);
     #endif
     while (~scanf ("%d%d",&n,&m))
     {
         init();
         for (int i = ; i < m; i++)
         {
             int u,v;
             scanf ("%d%d",&u,&v);
             Reverse(u,n);
             Reverse(u,u+n-v-);
         }
         dfs(root);
     }
     return ;
 }