首页 > 代码库 > BZOJ3196: Tyvj 1730 二逼平衡树

BZOJ3196: Tyvj 1730 二逼平衡树

2024-07-17 21:31:31   219人阅读

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  begin102  with t[k] do103   begin104     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  begin113   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  begin120   with t[k] do121    begin122     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  begin130   readln(x,y,z);131   writeln(query(1,x,y,z)+1);132  end;133 procedure solvefind;134  var l,r,mid:longint;135  begin136   readln(x,y,z);137   l:=0;r:=inf;138   while l<=r do139    begin140      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  begin147   readln(x,y);148   change(1,x,y);149   a[x]:=y;150  end;151 procedure solvepred;152  begin153   readln(x,y,z);154   writeln(findpred(1,x,y,z));155  end;156 procedure solvesucc;157  begin158   readln(x,y,z);159   writeln(findsucc(1,x,y,z));160  end;161 162 procedure init;163  begin164   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  begin171   for i:=1 to m do172    begin173      read(ch);174      case ch of175      1:solverank;176      2:solvefind;177      3:solvechange;178      4:solvepred;179      5:solvesucc;180      end;181    end;182  end;183 begin184   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

 

 


联系
我们