【BZOJ3224】普通平衡树（splay）

  1 var t:array[0..300000,0..1]of longint;
  2     sum,b,fa,num:array[0..300000]of longint;
  3     n,i,x,y,root,cnt,save,tmp,m:longint;
  4     flag:boolean;
  5 
  6 
  7 procedure pushup(x:longint);
  8 var l,r:longint;
  9 begin
 10  l:=t[x,0]; r:=t[x,1];
 11  sum[x]:=sum[l]+sum[r]+1;
 12 end;
 13 
 14 procedure rotate(x:longint;var k:longint);
 15 var y,z,l,r:longint;
 16 begin
 17  y:=fa[x]; z:=fa[y];
 18  if t[y,0]=x then l:=0
 19   else l:=1;
 20  r:=l xor 1;
 21  if y<>k then
 22  begin
 23   if t[z,0]=y then t[z,0]:=x
 24    else t[z,1]:=x;
 25  end
 26   else k:=x;
 27  fa[t[x,r]]:=y; fa[x]:=z; fa[y]:=x;
 28  t[y,l]:=t[x,r]; t[x,r]:=y;
 29  pushup(y);
 30  pushup(x);
 31 end;
 32 
 33 procedure splay(x:longint;var k:longint);
 34 var y,z:longint;
 35 begin
 36  while x<>k do
 37  begin
 38   y:=fa[x]; z:=fa[y];
 39   if y<>k then
 40   begin
 41    if (t[z,0]=y)xor(t[y,0]=x) then rotate(x,k)
 42     else rotate(y,k);
 43   end
 44    else k:=x;
 45   rotate(x,k);
 46  end;
 47 
 48 end;
 49 
 50 function pred(x:longint):longint;
 51 var k,last:longint;
 52 begin
 53  k:=root; last:=num[root];
 54  while k<>0 do
 55  begin
 56   if num[k]<x then begin last:=num[k]; k:=t[k,1]; end
 57    else k:=t[k,0];
 58  end;
 59  exit(last);
 60 end;
 61 
 62 function succ(x:longint):longint;
 63 var k,last:longint;
 64 begin
 65  k:=root; last:=num[root];
 66  while k<>0 do
 67  begin
 68   if num[k]>x then begin last:=num[k]; k:=t[k,0]; end
 69    else k:=t[k,1];
 70  end;
 71  exit(last);
 72 end;
 73 
 74 function rank(x:longint):longint;
 75 var k:longint;
 76 begin
 77  x:=pred(x);
 78  k:=root; rank:=0;
 79  while k>0 do
 80  begin
 81   if num[k]<=x then begin rank:=rank+sum[t[k,0]]+1; k:=t[k,1]; end
 82    else k:=t[k,0];
 83  end;
 84  inc(rank);
 85 end;
 86 
 87 function kth(x:longint):longint;
 88 var tmp,k:longint;
 89 begin
 90  k:=root;
 91  while true do
 92  begin
 93   tmp:=sum[t[k,0]]+1;
 94   if tmp=x then exit(k);
 95   if tmp>x then k:=t[k,0]
 96    else
 97    begin
 98     k:=t[k,1]; x:=x-tmp;
 99    end;
100  end;
101 end;
102 
103 function find(x:longint):longint;
104 var k:longint;
105 begin
106  k:=root;
107  while true do
108  begin
109   if num[k]=x then exit(k)
110    else if num[k]<x then k:=t[k,1]
111     else k:=t[k,0];
112  end;
113 end;
114 
115 procedure ins(x:longint);
116 var tmp,l,r,k1:longint;
117 begin
118  tmp:=rank(x);
119  l:=kth(tmp-1);
120  r:=kth(tmp);
121  splay(l,root);
122  splay(r,t[root,1]);
123  k1:=t[root,1];
124  inc(cnt); t[k1,0]:=cnt; fa[cnt]:=k1; sum[cnt]:=1; num[cnt]:=x;
125 // inc(sum[k1]);
126 // inc(sum[root]);
127 end;
128 
129 procedure del(x:longint);
130 var k1,k2,l,r:longint;
131 begin
132  tmp:=rank(x);
133  l:=kth(tmp-1);
134  r:=kth(tmp+1);
135  splay(l,root);
136  splay(r,t[root,1]);
137  k1:=t[root,1]; k2:=t[k1,0];
138  sum[k1]:=sum[t[k1,1]]+1; fa[k2]:=0; sum[k2]:=0;
139  t[k1,0]:=0;
140 
141  fa[k2]:=0; sum[k2]:=0; t[k2,0]:=0; t[k2,1]:=0;
142 
143 end;
144 
145 begin
146  assign(input,‘bzoj3224.in‘); reset(input);
147  assign(output,‘bzoj3224.out‘); rewrite(output);
148  readln(n);
149  num[1]:=maxlongint; sum[1]:=3; t[1,0]:=2; t[1,1]:=3;
150  num[2]:=-maxlongint; sum[2]:=1; fa[2]:=1;
151  num[3]:=maxlongint; sum[3]:=1; fa[3]:=1;
152 
153  root:=1; cnt:=3;
154  for i:=1 to n do
155  begin
156   readln(x,y);
157   case x of
158    1:
159    begin
160     ins(y);
161     inc(m);
162    end;
163    2:
164    begin
165     del(y);
166     dec(m);
167    end;
168 
169    3:writeln(rank(y)-1);
170 
171    4:writeln(num[kth(y+1)]);
172    5:writeln(pred(y));
173    6:writeln(succ(y));
174   end;
175  end;
176  close(input);
177  close(output);
178 end.