POJ 3481 Double Queue splay

  1 // File Name: poj3481.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年04月09日 星期四 14时41分43秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 100005
 26 using namespace std;
 27 
 28 struct SplayTree{
 29     int sz[maxn];
 30     int ch[maxn][2];
 31     int pre[maxn];
 32     int root , top1,top2;
 33     int ss[maxn],que[maxn];
 34     inline void Rotate(int x, int f){
 35         int y = pre[x];
 36         push_down(y);
 37         push_down(x);
 38         ch[y][!f] = ch[x][f];
 39         pre[ ch[x][f] ] = y  ; 
 40         pre[x] = pre[y];
 41         if( pre[x] ) ch[ pre[y] ][ ch[pre[y]][1] == y ] = x;  
 42         ch[x][f] = y ; 
 43         pre[y] = x; 
 44         push_up(y);
 45     }    
 46     inline void Splay(int x, int goal){
 47         push_down(x);
 48         while(pre[x] != goal){
 49             if(pre[pre[x]] == goal){
 50                 Rotate(x,ch[pre[x]][0] == x);
 51             }else{
 52                 int y = pre[x],z = pre[y];
 53                 int f = (ch[z][0] == y );
 54                 if(ch[y][f] == x){
 55                     Rotate(x,!f),Rotate(x,f);
 56                 }else{
 57                     Rotate(y,f),Rotate(x,f);
 58                 }
 59             }
 60         }
 61         push_up(x);
 62         if(goal == 0) root = x; 
 63     }      
 64     inline void RotateTo(int k ,int goal){
 65         int x = root ;
 66         push_down(x);
 67         while(sz[ch[x][0]] != k){
 68             if(k < sz[ch[x][0]]){
 69                 x = ch[x][0];
 70             }else{
 71                 k -= (sz[ch[x][0]] + 1);
 72                 x = ch[x][1];
 73             }
 74             push_down(x);
 75         }
 76         Splay(x,goal);
 77     }
 78     inline void erase(int x)
 79     {
 80        int father = pre[x];
 81        int head = 0 , tail =0 ; 
 82        for(que[tail++] = x ; head < tail ; head ++){
 83           ss[top2++] = que[head];
 84           if(ch[que[head]][0] )  que[tail ++] = ch[que[head]][0];
 85           if(ch[que[head]][1] )  que[tail ++] = ch[que[head]][1];
 86        }
 87        ch[father][ch[father][1] == x] =0 ; 
 88        push_up(father);
 89     }
 90     inline void NewNode(int &x, int key ,int val){
 91         if(top2) x = ss[--top2];
 92         else x = ++top1;
 93         ch[x][0] = ch[x][1] = pre[x] = 0 ; 
 94         sz[x] = 1; 
 95         
 96         vals[x] = val;
 97         keys[x] = key ;
 98     }
 99     
100     void init(){
101         ch[0][0] = ch[0][1] = sz[0] = pre[0] = 0 ;
102         root = top1 =0 ; 
103         NewNode(root,0,0);
104         NewNode(ch[root][1],1e9,0);
105         sz[root] = 2;
106         pre[ch[root][1]] = root; 
107     }
108     void push_up(int x){
109         sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]];
110     }
111     void push_down(int x){
112     
113     }
114     void insert(int key,int val){
115          int x = root ;
116          for(;;){
117              int f = (key > keys[x]);
118              if(ch[x][f] == 0 ){
119                  NewNode(ch[x][f],key,val);
120                  pre[ch[x][f]] = x; 
121                  Splay(ch[x][f],0);
122                  return ; 
123              }else{
124                 x = ch[x][f];
125              }
126          }
127     }
128     void Del(int rank){
129         //printf("%d***
",rank);
130         RotateTo(rank-1,0);
131         RotateTo(rank+1,root);
132     //    printf("%d %d
",keys[root],keys[ch[root][1]]);
133         printf("%d
",vals[ch[ch[root][1]][0]]);
134         erase(ch[ch[root][1]][0]);
135         push_up(root);
136     //    printf("****");
137     }
138     int keys[maxn];
139     int vals[maxn];
140 }spt;
141 int n ;
142 int key,val;
143 int main(){
144       spt.init();
145       while(scanf("%d",&n) != EOF && n )
146       {
147          int sz = spt.sz[spt.root];
148          if(n == 2 )
149          {
150             if(sz> 2){
151                 spt.Del(sz-2);
152             }else{
153               printf("0
");
154             }
155          }else if(n == 3){
156             if(sz> 2){
157                 spt.Del(1);
158             }else{
159               printf("0
");
160             }
161          }else{
162             scanf("%d %d",&val,&key);
163             spt.insert(key,val);
164          }
165     //     sz = spt.sz[spt.root];
166     //     printf("%d
",sz);
167       }
168 return 0;
169 }