BZOJ3196: Tyvj 1730 二逼平衡树

3196: Tyvj 1730 二逼平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 775 Solved: 316
[Submit][Status]

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围：n,m<=50000

2.序列中每个数的数据范围：[0,1e8]

3.虽然原题没有，但事实上5操作的k可能为负数

题解：

需要注意几点：

1.一个数的rank是比它小的数的个数+1

2.要使用正确的二分查找

在查找区间第k小的时候，相当于在rank数组中查询k，如果k出现了那么返回k最后出现的位置否则返回一个位置在这个位置插入k后，rank数组仍然有序

就如上一篇博文中的YES-RIGHT NO-LEFT类型的二分查找

3.求前驱后继的代码要想好怎么写

以pred为例，节点为0时返回-inf，关键值<=节点值则到左子树去寻找，否则到右子树并且判断返回值是否为-inf，

是的话说明右子树为空，而该节点是比关键值小的一个值，没有比它大的了，所以前驱就是该节点

代码：

  1 uses math;
  2 const maxn=50000+1000;inf=1000000000;
  3 type node=record
  4      l,r,lch,rch,rt,mid:longint;
  5      end;
  6 var t:array[0..8*maxn] of node;
  7     l,r,s,w,rnd,v,a:array[0..20*maxn] of longint;
  8     i,n,m,x,y,z,tot,ch:longint;
  9 procedure pushup(k:longint);
 10  begin
 11    s[k]:=s[l[k]]+s[r[k]]+w[k];
 12  end;
 13 procedure rturn(var k:longint);
 14  var t:longint;
 15  begin
 16    t:=l[k];l[k]:=r[t];r[t]:=k;s[t]:=s[k];pushup(k);k:=t;
 17  end;
 18 procedure lturn(var k:longint);
 19  var t:longint;
 20  begin
 21    t:=r[k];r[k]:=l[t];l[t]:=k;s[t]:=s[k];pushup(k);k:=t;
 22  end;
 23 procedure ins(var k,num:longint);
 24  begin
 25   if k=0 then
 26    begin
 27     inc(tot);k:=tot;v[k]:=num;s[k]:=1;w[k]:=1;l[k]:=0;r[k]:=0;
 28     rnd[k]:=random(maxlongint);exit;
 29    end;
 30   inc(s[k]);
 31   if num=v[k] then inc(w[k])
 32   else if num<v[k] then begin ins(l[k],num);if rnd[l[k]]<rnd[k] then rturn(k);end
 33   else begin ins(r[k],num);if rnd[r[k]]<rnd[k] then lturn(k);end;
 34  end;
 35 procedure del(var k,num:longint);
 36  begin
 37   if v[k]=num then
 38    begin
 39     if w[k]>1 then begin dec(w[k]);dec(s[k]);exit;end;
 40     if l[k]*r[k]=0 then k:=l[k]+r[k]
 41     else if rnd[l[k]]<rnd[r[k]] then begin rturn(k);del(k,num);end
 42     else begin lturn(k);del(k,num);end;
 43     exit;
 44    end;
 45   dec(s[k]);
 46   if num<v[k] then del(l[k],num) else del(r[k],num);
 47  end;
 48 procedure build(k,x,y:longint);
 49  var i:longint;
 50  begin
 51   with t[k] do
 52    begin
 53      l:=x;r:=y;mid:=(l+r)>>1;
 54      for i:=l to r do ins(rt,a[i]);
 55      if l=r then exit;
 56      lch:=k<<1;rch:=k<<1+1;
 57      build(lch,l,mid);build(rch,mid+1,r);
 58    end;
 59  end;
 60 procedure change(k,x,y:longint);
 61  begin
 62   with t[k] do
 63    begin
 64      del(rt,a[x]);ins(rt,y);
 65      if l=r then exit;
 66      if x<=mid then change(lch,x,y)
 67      else change(rch,x,y);
 68    end;
 69  end;
 70 function pred(k,num:longint):longint;
 71  begin
 72   if k=0 then exit(-inf);
 73   if num<=v[k] then pred:=pred(l[k],num)
 74   else
 75      begin
 76       pred:=pred(r[k],num);
 77       if pred=-inf then pred:=v[k];
 78      end;
 79  end;
 80 function succ(k,num:longint):longint;
 81  begin
 82   if k=0 then exit(inf);
 83   if num>=v[k] then succ:=succ(r[k],num)
 84   else
 85       begin
 86        succ:=succ(l[k],num);
 87        if succ=inf then succ:=v[k];
 88       end;
 89  end;
 90 function findpred(k,x,y,z:longint):longint;
 91  begin
 92  with t[k] do
 93   begin
 94     if (l=x) and (r=y) then exit(pred(rt,z));
 95     if y<=mid then exit(findpred(lch,x,y,z))
 96     else if x>mid then exit(findpred(rch,x,y,z))
 97     else exit(max(findpred(lch,x,mid,z),findpred(rch,mid+1,y,z)));
 98   end;
 99  end;
100 function findsucc(k,x,y,z:longint):longint;
101  begin
102  with t[k] do
103   begin
104     if (l=x) and (r=y) then exit(succ(rt,z));
105     if y<=mid then exit(findsucc(lch,x,y,z))
106     else if x>mid then exit(findsucc(rch,x,y,z))
107     else exit(min(findsucc(lch,x,mid,z),findsucc(rch,mid+1,y,z)));
108   end;
109  end;
110 
111 function rank(k,num:longint):longint;
112  begin
113   if k=0 then exit(0);
114   if num=v[k] then exit(s[l[k]])
115   else if num<v[k] then exit(rank(l[k],num))
116   else exit(s[l[k]]+w[k]+rank(r[k],num));
117  end;
118 function query(k,x,y,num:longint):longint;
119  begin
120   with t[k] do
121    begin
122     if (l=x) and (r=y) then exit(rank(rt,num));
123     if y<=mid then exit(query(lch,x,y,num))
124     else if x>mid then exit(query(rch,x,y,num))
125     else exit(query(lch,x,mid,num)+query(rch,mid+1,y,num));
126    end;
127  end;
128 procedure solverank;
129  begin
130   readln(x,y,z);
131   writeln(query(1,x,y,z)+1);
132  end;
133 procedure solvefind;
134  var l,r,mid:longint;
135  begin
136   readln(x,y,z);
137   l:=0;r:=inf;
138   while l<=r do
139    begin
140      mid:=(l+r)>>1;
141      if query(1,x,y,mid)+1>z then r:=mid-1 else l:=mid+1;
142    end;
143  writeln(r);
144  end;
145 procedure solvechange;
146  begin
147   readln(x,y);
148   change(1,x,y);
149   a[x]:=y;
150  end;
151 procedure solvepred;
152  begin
153   readln(x,y,z);
154   writeln(findpred(1,x,y,z));
155  end;
156 procedure solvesucc;
157  begin
158   readln(x,y,z);
159   writeln(findsucc(1,x,y,z));
160  end;
161 
162 procedure init;
163  begin
164   tot:=0;
165   readln(n,m);
166   for i:=1 to n do read(a[i]);readln;
167   build(1,1,n);
168  end;
169 procedure main;
170  begin
171   for i:=1 to m do
172    begin
173      read(ch);
174      case ch of
175      1:solverank;
176      2:solvefind;
177      3:solvechange;
178      4:solvepred;
179      5:solvesucc;
180      end;
181    end;
182  end;
183 begin
184   assign(input,'input.txt');assign(output,'output.txt');
185   reset(input);rewrite(output);
186   init;
187   main;
188   close(input);close(output);
189 end.

View Code