首页 > 代码库 > BZOJ1901: Zju2112 Dynamic Rankings
BZOJ1901: Zju2112 Dynamic Rankings
1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 4231 Solved: 1764
[Submit][Status]
Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
Input
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
6
HINT
20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中，m,n≤10000。
Source
题解：
写的很好写，尼玛怎么就是WA！和暴力对拍了没发现问题啊！
代码：
1 const maxn=50000+1000; 2 type node=record 3 l,r,lch,rch,rt,mid:longint; 4 end; 5 var t:array[0..4*maxn] of node; 6 l,r,s,w,rnd,v,a:array[0..50*maxn] of longint; 7 i,n,m,x,y,z,tot:longint; 8 ch:char; 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 // writeln(l[100],‘ ‘,r[100],‘ ‘,rnd[100],‘ ‘,num); 41 // writeln(l[93],‘ ‘,r[93],‘ ‘,rnd[93],‘ ‘,num); 42 if l[k]*r[k]=0 then k:=l[k]+r[k] 43 else if rnd[l[k]]<rnd[r[k]] then begin rturn(k);del(k,num);end 44 else begin lturn(k);del(k,num);end; 45 exit; 46 end; 47 dec(s[k]); 48 if num<v[k] then del(l[k],num) else del(r[k],num); 49 end; 50 procedure build(k,x,y:longint); 51 var i:longint; 52 begin 53 with t[k] do 54 begin 55 l:=x;r:=y;mid:=(l+r)>>1; 56 for i:=l to r do ins(rt,a[i]); 57 if l=r then exit; 58 lch:=k<<1;rch:=k<<1+1; 59 build(lch,l,mid);build(rch,mid+1,r); 60 end; 61 end; 62 procedure print(x:longint); 63 begin 64 if x=0 then exit; 65 print(l[x]); 66 write(x,‘ ‘,v[x],‘!‘); 67 print(r[x]); 68 end; 69 procedure change(k,x,y:longint); 70 begin 71 with t[k] do 72 begin 73 // writeln(k,‘ ‘,l,‘ ‘,r,‘ ‘,rt); 74 // print(rt);writeln; 75 del(rt,a[x]);ins(rt,y); 76 if l=r then exit; 77 if x<=mid then change(lch,x,y) 78 else change(rch,x,y); 79 end; 80 end; 81 function rank(k,num:longint):longint; 82 begin 83 if k=0 then exit(0); 84 if num<v[k] then exit(rank(l[k],num)) 85 else exit(s[l[k]]+w[k]+rank(r[k],num)); 86 end; 87 function query(k,x,y,num:longint):longint; 88 begin 89 with t[k] do 90 begin 91 //writeln(k,‘ ‘,l,‘ ‘,r,‘ ‘,x,‘ ‘,y,‘ ‘,num); 92 if (l=x) and (r=y) then exit(rank(rt,num)); 93 if y<=mid then exit(query(lch,x,y,num)) 94 else if x>mid then exit(query(rch,x,y,num)) 95 else exit(query(lch,x,mid,num)+query(rch,mid+1,y,num)); 96 end; 97 end; 98 procedure solvechange; 99 begin100 readln(x,y);101 change(1,x,y);102 a[x]:=y;103 end;104 procedure solveask;105 var l,r,mid:longint;106 begin107 readln(x,y,z);108 l:=0;r:=1000000000;109 while l<r do110 begin111 mid:=(l+r)>>1;112 if query(1,x,y,mid)>=z then r:=mid else l:=mid+1;113 end;114 writeln(l);115 end;116 procedure init;117 begin118 readln(n,m);119 for i:=1 to n do read(a[i]);readln;120 build(1,1,n);121 end;122 procedure main;123 begin124 for i:=1 to m do125 begin126 read(ch);//writeln(i,‘ ‘,ch);127 case ch of128 ‘C‘:solvechange;129 ‘Q‘:solveask;130 end;131 end;132 end;133 begin134 assign(input,‘input.txt‘);assign(output,‘output.txt‘);135 reset(input);rewrite(output);136 init;137 main;138 close(input);close(output);139 end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。