HDU1890-Robotic Sort-Splay

  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 = 2e5+10;
 10 const int INF = 0x3f3f3f3f;
 11 
 12 int pre[maxn],ch[maxn][2],key[maxn],size[maxn];
 13 int root,tot1;
 14 int rev[maxn];
 15 int s[maxn],tot2;
 16 int N;
 17 
 18 struct Node{
 19     int num,id;
 20     bool operator < (const Node &rhs) const
 21     {
 22         if(num == rhs.num) return id < rhs.id;
 23         else return num < rhs.num;
 24     }
 25 }node[maxn];
 26 
 27 void Treavel(int x)
 28 {
 29     if(x)
 30     {
 31         Treavel(ch[x][0]);
 32         printf("结点:%2d: 左儿子 %2d 右儿子 %2d 父结点 %2d size= %2d val=%2d\n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
 33         Treavel(ch[x][1]);
 34     }
 35 }
 36 
 37 void debug()
 38 {
 39     printf("root:%d\n",root);
 40     Treavel(root);
 41 }
 42 
 43 void NewNode(int &o,int father,int k)
 44 {
 45     o = k;
 46     pre[o] = father;
 47     ch[o][0] = ch[o][1] = 0;
 48     rev[o] = 0;
 49     size[o] = 1;
 50 }
 51 void update_rev(int o)
 52 {
 53     if(!o) return ;
 54     swap(ch[o][0],ch[o][1]);
 55     rev[o] ^= 1;
 56 }
 57 void push_up(int o)
 58 {
 59     int lson = ch[o][0],rson = ch[o][1];
 60     size[o] = size[lson]+size[rson] + 1;
 61 }
 62 void push_down(int o)
 63 {
 64     if(rev[o])
 65     {
 66         update_rev(ch[o][0]);
 67         update_rev(ch[o][1]);
 68         rev[o] = 0;
 69     }
 70 }
 71 void Build(int &x,int l,int r,int father)
 72 {
 73     if(l > r) return ;
 74     int mid = (l+r)>>1;
 75     NewNode(x,father,mid);
 76     Build(ch[x][0],l,mid-1,x);
 77     Build(ch[x][1],mid+1,r,x);
 78     push_up(x);
 79 }
 80 void Init()
 81 {
 82     root = tot1 = tot2 = 0;
 83     ch[root][0] = ch[root][1] = size[root] = pre[root] = 0;
 84     rev[root] = 0;
 85     NewNode(root,0,N+1);
 86     NewNode(ch[root][1],root,N+2);
 87 
 88     Build(Key_value,1,N,ch[root][1]);
 89     push_up(ch[root][1]);
 90     push_up(root);
 91 }
 92 void Rotate(int x,int kind)
 93 {
 94     int y = pre[x];
 95     push_down(y);
 96     push_down(x);
 97     ch[y][!kind] = ch[x][kind];
 98     pre[ch[x][kind] ] = y;
 99     if(pre[y])
100         ch[pre[y] ][ch[pre[y]][1]==y ] = x;
101     pre[x] = pre[y];
102     ch[x][kind] = y;
103     pre[y] = x;
104     push_up(y);
105 }
106 void Splay(int x,int goal)
107 {
108     push_down(x);
109     while(pre[x] != goal)
110     {
111         if(pre[pre[x] ] == goal)
112         {
113             push_down(pre[x]);
114             push_down(x);
115             Rotate(x,ch[pre[x]][0]==x);
116         }
117         else
118         {
119             push_down(pre[pre[x] ]);
120             push_down(pre[x]);
121             push_down(x);
122             int y = pre[x];
123             int kind = ch[pre[y] ][0] == y;
124             if(ch[y][kind] == x)
125             {
126                 Rotate(x,!kind);
127                 Rotate(x,kind);
128             }
129             else
130             {
131                 Rotate(y,kind);
132                 Rotate(x,kind);
133             }
134         }
135     }
136     push_up(x);
137     if(goal == 0) root = x;
138 }
139 int Get_kth(int x,int k)
140 {
141     push_down(x);
142     int t = size[ch[x][0]] + 1;
143     if(t==k) return x;
144     if(t > k) return Get_kth(ch[x][0],k);
145     else return Get_kth(ch[x][1],k-t);
146 }
147 int Get_next(int x)
148 {
149     push_down(x);
150     if(ch[x][1] == 0) return -1;
151     x = ch[x][1];
152     while(ch[x][0])
153     {
154         x = ch[x][0];
155         push_down(x);
156     }
157     return x;
158 }
159 int main()
160 {
161     while(scanf("%d",&N) && N)
162     {
163         for(int i=1;i<=N;i++)
164         {
165             scanf("%d",&node[i].num);
166             node[i].id = i;
167         }
168         sort(node+1,node+N+1);
169         Init();
170         for(int i=1;i<=N;i++)
171         {
172             Splay(node[i].id,0);
173             printf("%d%s",size[ch[root][0]],i==N?"":" ");
174             Splay(Get_kth(root,i),0);
175             Splay(Get_next(node[i].id),root);
176             update_rev(Key_value);
177         }
178         printf("\n");
179     }
180 }