HDU 1890 Robotic Sort

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef pair<int,int> pii;
  4 const int maxn = 200010;
  5 struct SplayTree{
  6     int ch[maxn][2],fa[maxn],sz[maxn],root,tot;
  7     int val[maxn],id[maxn],flip[maxn],mp[maxn];
  8     inline void pushdown(int x){
  9         if(flip[x]){
 10             flip[ch[x][0]] ^= 1;
 11             flip[ch[x][1]] ^= 1;
 12             swap(ch[x][0],ch[x][1]);
 13             flip[x] = 0;
 14         }
 15     }
 16     inline void pushup(int x){
 17         sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
 18     }
 19     void newnode(int &x,int key,int f){
 20         x = ++tot;
 21         flip[x] = ch[x][0] = ch[x][1] = 0;
 22         fa[x] = f;
 23         sz[x] = 1;
 24         val[x] = key;
 25     }
 26     void rotate(int x,int kd){
 27         int y = fa[x];
 28         pushdown(y);
 29         pushdown(x);
 30         ch[y][kd^1] = ch[x][kd];
 31         fa[ch[x][kd]] = y;
 32         fa[x] = fa[y];
 33         fa[y] = x;
 34         ch[x][kd] = y;
 35         if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x;
 36         pushup(y);
 37     }
 38     void splay(int x,int goal){
 39         pushdown(x);
 40         while(fa[x] != goal){
 41             pushdown(fa[fa[x]]);
 42             pushdown(fa[x]);
 43             pushdown(x);
 44             if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]);
 45             else{
 46                 int y = fa[x],z = fa[y],s = (y == ch[z][0]);
 47                 if(x == ch[y][s]){
 48                     rotate(x,s^1);
 49                     rotate(x,s);
 50                 }else{
 51                     rotate(y,s);
 52                     rotate(x,s);
 53                 }
 54             }
 55         }
 56         if(!goal) root = x;
 57         pushup(x);
 58     }
 59     void select(int k,int goal){
 60         int x = root;
 61         pushdown(x);
 62         while(sz[ch[x][0]] + 1 != k){
 63             if(k < sz[ch[x][0]] + 1) x = ch[x][0];
 64             else{
 65                 k -= sz[ch[x][0]] + 1;
 66                 x = ch[x][1];
 67             }
 68             pushdown(x);
 69         }
 70         splay(x,goal);
 71     }
 72     void build(int &x,int L,int R,int f){
 73         if(L > R) return;
 74         int mid = (L + R)>>1;
 75         newnode(x,num[id[mid]].first,f);
 76         mp[id[mid]] = x;
 77         build(ch[x][0],L,mid-1,x);
 78         build(ch[x][1],mid + 1,R,x);
 79         pushup(x);
 80     }
 81     void init(int n){
 82         val[0] = fa[0] = sz[0] = tot = 0;
 83         ch[0][0] = ch[0][1] = flip[0] = 0;
 84         for(int i = 1; i <= n; ++i){
 85             scanf("%d",&num[i].first);
 86             num[i].second = i;
 87         }
 88         sort(num + 1,num + n + 1);
 89         for(int i = 1; i <= n; ++i) id[num[i].second] = i;
 90         build(root,1,n,0);
 91     }
 92     void removeRoot(){
 93         int x = root;
 94         pushdown(x);
 95         if(ch[root][1]){
 96             root = ch[root][1];
 97             select(1,0);
 98             ch[root][0] = ch[x][0];
 99             if(ch[root][0]) fa[ch[root][0]] = root;
100         }else root = ch[root][0];
101         fa[root] = 0;
102         pushup(root);
103     }
104     void solve(int n){
105         for(int i = 1; i <= n; ++i){
106             splay(mp[i],0);
107             printf("%d%c",i + sz[ch[root][0]],i == n?‘\n‘:‘ ‘);
108             flip[ch[root][0]] ^= 1;
109             removeRoot();
110         }
111     }
112     pii num[maxn];
113 }spt;
114 int main(){
115     int n;
116     while(scanf("%d",&n),n){
117         spt.init(n);
118         spt.solve(n);
119     }
120     return 0;
121 }