BZOJ/1901.pas

   1 type
   2   treapnode=record
   3               v,p,size,l,r:longint;
   4               //v: value, p: priority, l: lson, r: rson
   5             end;
   6
   7   segment=record
   8             l,r:longint;
   9             bst:longint; //bst: root of the treap
  10             lson,rson:longint;
  11           end;
  12
  13 var
  14   treap:array [0..1100000] of treapnode;
  15   segtree:array [0..100100] of segment;
  16   pos,top,x,root:longint;
  17   data:array [0..50010] of longint;
  18
  19 //Implementation of Treap
  20
  21 procedure new_treap(v,root:longint);
  22 begin
  23   treap[root].p:=random(maxlongint);
  24   treap[root].l:=0;
  25   treap[root].r:=0;
  26   treap[root].v:=v;
  27   treap[root].size:=1;
  28 end;
  29
  30 procedure RightRotate(var p:longint);
  31 var
  32   q:longint;
  33
  34 begin
  35   q:=treap[p].l;
  36   treap[p].l:=treap[q].r;
  37   treap[q].r:=p;
  38   p:=q;
  39 end;
  40
  41 procedure LeftRotate(var p:longint);
  42 var
  43   q:longint;
  44
  45 begin
  46   q:=treap[p].r;
  47   treap[p].r:=treap[q].l;
  48   treap[q].l:=p;
  49   p:=q;
  50 end;
  51
  52 procedure update(p:longint);
  53 begin
  54   if p=0 then exit;
  55   treap[p].size:=treap[treap[p].l].size+treap[treap[p].r].size+1;
  56 end;
  57
  58 procedure add(v:longint; var root:longint); overload;
  59 begin
  60   if root=0 then
  61     begin
  62       inc(pos);
  63       root:=pos;
  64       new_treap(v,root);
  65       exit;
  66     end;
  67   if v<treap[root].v then
  68     begin
  69       add(v,treap[root].l);
  70       if treap[treap[root].l].p<treap[root].p then RightRotate(root);
  71     end
  72   else
  73     begin
  74       add(v,treap[root].r);
  75       if treap[treap[root].r].p<treap[root].p then LeftRotate(root);
  76     end;
  77   update(root);
  78   update(treap[root].l);
  79   update(treap[root].r);
  80 end;
  81
  82 procedure del(k:longint; var root:longint);
  83 begin
  84   if k<treap[root].v then del(k,treap[root].l) else
  85     if k>treap[root].v then del(k,treap[root].r) else
  86       begin
  87         if (treap[root].l=0) and (treap[root].r=0) then
  88           begin
  89             root:=0;
  90             exit;
  91           end;
  92         if (treap[root].l>0) and (treap[root].r=0) then root:=treap[root].l else
  93           if (treap[root].l=0) and (treap[root].r>0) then root:=treap[root].r else
  94             begin
  95               if treap[treap[root].l].p<treap[root].p then
  96                 begin
  97                   RightRotate(root);
  98                   del(k,treap[root].r);
  99                 end
 100               else
 101                 begin
 102                   LeftRotate(root);
 103                   del(k,treap[root].l);
 104                 end;
 105             end;
 106       end;
 107   update(root);
 108   update(treap[root].l);
 109   update(treap[root].r);
 110 end;
 111
 112 function succ(k,root:longint):longint;
 113 begin
 114   if root=0 then exit(0);
 115   if k>=treap[root].v then exit(treap[treap[root].l].size+1+succ(k,treap[root].r));
 116   exit(succ(k,treap[root].l));
 117 end;
 118
 119 //end of Treap
 120
 121 //Implementation of SegmentTree
 122
 123 function mid(root:longint):longint; inline;
 124 begin
 125   exit((segtree[root].l+segtree[root].r) shr 1);
 126 end;
 127
 128 procedure BuildTree(l,r:longint; var root:longint);
 129 var
 130   i:longint;
 131
 132 begin
 133   inc(top);
 134   root:=top;
 135   segtree[root].l:=l;
 136   segtree[root].r:=r;
 137   segtree[root].bst:=0;
 138   segtree[root].lson:=0;
 139   segtree[root].rson:=0;
 140   for i:=l to r do add(data[i],segtree[root].bst);
 141   if l=r then exit;
 142   BuildTree(l,mid(root),segtree[root].lson);
 143   BuildTree(mid(root)+1,r,segtree[root].rson);
 144 end;
 145
 146 procedure change(p,v,root:longint); inline;
 147 begin
 148   del(p,segtree[root].bst);
 149   add(v,segtree[root].bst);
 150 end;
 151
 152 procedure modify(p,v,root:longint); overload;
 153 begin
 154   change(data[p],v,root);
 155   if segtree[root].l=segtree[root].r then exit;
 156   if p<=mid(root) then modify(p,v,segtree[root].lson) else modify(p,v,segtree[root].rson);
 157 end;
 158
 159 function askrank(l,r,v,root:longint):longint;
 160 begin
 161   if (segtree[root].l>=l) and (segtree[root].r<=r) then exit(succ(v,segtree[root].bst));
 162   if r<=mid(root) then exit(askrank(l,r,v,segtree[root].lson)) else
 163     if l>mid(root) then exit(askrank(l,r,v,segtree[root].rson)) else
 164       exit(askrank(l,r,v,segtree[root].lson)+askrank(l,r,v,segtree[root].rson));
 165 end;
 166
 167 function ask(l,r,v:longint):longint; overload;
 168 var
 169   p,q,mid,t1,t2:longint;
 170
 171 begin
 172   p:=0;
 173   q:=maxlongint shr 1;
 174   while p<=q do
 175     begin
 176       mid:=(p+q) shr 1;
 177       t1:=askrank(l,r,mid,1);
 178       t2:=askrank(l,r,mid-1,1);
 179       if (v<=t1) and (v>t2) then exit(mid);
 180       if t1<v then p:=mid+1 else q:=mid;
 181     end;
 182 end;
 183
 184 procedure modify(p,v:longint); overload;
 185 begin
 186   modify(p,v,1);
 187   data[p]:=v;
 188 end;
 189
 190 procedure main;
 191 var
 192   n,m,i,x,y,k:longint;
 193   order:char;
 194
 195 begin
 196   pos:=0;
 197   top:=0;
 198   readln(n,m);
 199   for i:=1 to n do read(data[i]);
 200   readln;
 201   root:=1;
 202   BuildTree(1,n,root);
 203   repeat
 204     read(order);
 205     case order of
 206       'C':begin
 207             readln(x,k);
 208             modify(x,k);
 209           end;
 210       'Q':begin
 211             readln(x,y,k);
 212             writeln(ask(x,y,k));
 213           end;
 214     end;
 215     dec(m);
 216   until m=0;
 217 end;
 218
 219 begin
 220   randomize;
 221 //readln(x);
 222   x:=1;
 223 //This is the difference between BZOJ1901&ZOJ2112
 224   repeat
 225     dec(x);
 226     main;
 227   until x=0;
 228 end.