1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 5268  Solved: 2207

[Submit][Status][Discuss]

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

Sample Output

3 6

HINT

20%的数据中,m,n≤100; 40%的数据中,m,n≤1000; 100%的数据中,m,n≤10000。

Source

题解:人生中的一个A掉的树套树,就是线段树套Treap树,线段树每一个点所代表的不再是一个简单的点,而是一棵Treap树,然后每次修改将要牵扯到logN棵树,然后每棵树复杂度为logN,所以修改操作是log^2N的,然后就是区间第K大了,显然,查询区间内某数排名在上面的基础上并不难做(其实就是查询有多少个数字小于它然后再+1),然后就是确定最大最小值然后二分一下,这样一来复杂度为log^3N,然后然后没别的了(Hansbug:此程序里面的删除操作和求区间第K大操作是按照hzwer神犇的写法来写的orz)

  1 /**************************************************************
  2     Problem: 1901
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:4756 ms
  7     Memory:31476 kb
  8 ****************************************************************/
  9  
 10 var
 11         i,j,k,l,m,n,tot:longint;ch:char;
 12         a,b,c,d,e,lef,rig,fix:array[0..1000000] of longint;
 13 function max(x,y:longint):longint;
 14         begin
 15                 if x>y then max:=x else max:=Y;
 16         end;
 17 function min(x,y:longint):longint;
 18         begin
 19                 if x<y then min:=x else min:=y;
 20         end;
 21 procedure swap(var x,y:longint);
 22         var z:longint;
 23         begin
 24                 z:=x;x:=y;y:=z;
 25         end;
 26 function newp(x:longint):longint;
 27         begin
 28                 inc(tot);newp:=tot;
 29                 c[tot]:=x;b[tot]:=1;
 30                 lef[tot]:=0;rig[tot]:=0;
 31                 fix[tot]:=random(maxlongint);
 32         end;
 33 procedure rt(var x:longint);
 34         var f,l:longint;
 35         begin
 36                 if (x=0) or (lef[x]=0) then exit;
 37                 b[lef[x]]:=b[x];b[x]:=b[rig[x]]+b[rig[lef[x]]]+1;
 38                 f:=x;l:=lef[x];
 39                 lef[f]:=rig[l];
 40                 rig[l]:=f;
 41                 x:=l;
 42         end;
 43 procedure lt(var x:longint);
 44         var f,r:longint;
 45         begin
 46                 if (x=0) or (rig[x]=0) then exit;
 47                 b[rig[x]]:=b[x];b[x]:=b[lef[x]]+b[lef[rig[x]]]+1;
 48                 f:=x;r:=rig[x];
 49                 rig[f]:=lef[r];
 50                 lef[r]:=f;
 51                 x:=r;
 52         end;
 53 procedure ins(var x:longint;y:longint);
 54         begin
 55                 if x=0 then
 56                         begin
 57                                 x:=newp(y);
 58                                 exit;
 59                         end;
 60                 if y<c[x] then
 61                         begin
 62                                 ins(lef[x],y);
 63                                 b[x]:=b[lef[x]]+b[rig[x]]+1;
 64                                 if fix[lef[x]]<fix[x] then rt(x);
 65                         end
 66                 else
 67                         begin
 68                                 ins(rig[x],y);
 69                                 b[x]:=b[lef[x]]+b[rig[x]]+1;
 70                                 if fix[rig[x]]<fix[x] then lt(x);
 71                         end;
 72         end;
 73 procedure del(var x:longint;y:longint);
 74         begin
 75                 if x=0 then exit;
 76                 if c[x]=y then
 77                         begin
 78                                 if lef[x]=0  then x:=rig[x] else
 79                                 if rig[x]=0 then x:=lef[x] else
 80                                 if fix[lef[x]]>fix[rig[x]] then
 81                                         begin
 82                                                 lt(x);
 83                                                 del(lef[x],y);
 84                                                 b[x]:=b[lef[x]]+b[rig[x]]+1;
 85                                         end
 86                                 else begin
 87                                         rt(x);
 88                                         del(rig[x],y);
 89                                         b[x]:=b[lef[x]]+b[rig[x]]+1;
 90                                      end;
 91                         end
 92                 else if y<c[x] then
 93                         begin
 94                                 del(lef[x],y);
 95                                 b[x]:=b[lef[x]]+b[rig[x]]+1;
 96                         end
 97                 else    begin
 98                                 del(rig[x],y);
 99                                 b[x]:=b[rig[x]]+b[lef[x]]+1;
100                         end;
101         end;
102 function grank(x,y:longint):longint;
103         begin
104                 if x=0 then exit(0);
105                 if c[x]>=y then exit(grank(lef[x],y)) else exit(b[lef[x]]+1+grank(rig[x],y));
106         end;
107 function gmin(x:longint):longint;
108         begin
109                 if x=0 then exit(maxlongint);
110                 while lef[x]<>0 do x:=lef[x];
111                 exit(c[x]);
112         end;
113 function gmax(x:longint):longint;
114         begin
115                 if x=0 then exit(-maxlongint);
116                 while rig[x]<>0 do x:=rig[x];
117                 exit(c[x]);
118         end;
119 function getrank(z,x,y,l,r,t:longint):longint;
120         begin
121                 if l>r then exit(0);
122                 if (x=l) and (y=r) then exit(grank(a[z],t));
123                 exit(getrank(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t)+
124                 getrank(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t));
125         end;
126 function getmin(z,x,y,l,r:longint):longint;
127         begin
128                 if l>r then exit(maxlongint);
129                 if (x=l) and (y=r) then exit(gmin(a[z]));
130                 exit(min(getmin(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),
131                 getmin(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
132         end;
133 function getmax(z,x,y,l,r:longint):longint;
134         begin
135                 if l>r then exit(-maxlongint);
136                 if (x=l) and (y=r) then exit(gmax(a[z]));
137                 exit(max(getmax(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),
138                 getmax(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
139         end;
140 function rankget(x,y,z:longint):longint;
141         var l,r,m:longint;
142         begin
143                 l:=getmin(1,1,n,x,y);
144                 r:=getmax(1,1,n,x,y);
145                 while l<=r do
146                         begin
147                                 m:=(l+r) div 2;
148                                 if getrank(1,1,n,x,y,m)<=(z-1) then
149                                         begin
150                                                 l:=m+1;
151                                                 rankget:=m;
152                                         end
153                                 else r:=m-1;
154                         end;
155         end;
156 procedure built(z,x,y:longint);
157         begin
158                 if x=y then d[x]:=z else
159                         begin
160                                 built(z*2,x,(x+y) div 2);
161                                 built(z*2+1,(x+y) div 2+1,y);
162                         end;
163                 a[z]:=0;
164         end;
165 procedure putin(x,y:longint);
166         begin
167                 x:=d[x];
168                 while x>0 do
169                         begin
170                                 ins(a[x],y);
171                                 x:=x div 2;
172                         end;
173         end;
174 procedure change(x,y:longint);
175         var z:longint;
176         begin
177                 x:=d[x];
178                 z:=c[a[x]];
179                 while x>0 do
180                         begin
181                                 del(a[x],z);
182                                 ins(a[x],y);
183                                 x:=x div 2;
184                         end;
185         end;
186 begin
187         readln(n,m);
188         built(1,1,n);
189         for i:=1 to n do
190                 begin
191                         read(j);
192                         putin(i,j);
193                 end;
194         readln;
195         for i:=1 to m do
196                 begin
197                         read(ch);
198                         case upcase(ch) of
199                                 'Q':begin
200                                         readln(j,k,l);
201                                         writeln(rankget(j,k,l));
202                                 end;
203                                 'C':begin
204                                         readln(j,k);
205                                         change(j,k);
206                                 end;
207                         end;
208  
209                 end;
210 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿杜的世界

【译】Java 8的新特性—终极版1. 简介2. Java语言的新特性3. Java编译器的新特性4. Java官方库的新特性5. 新的Java工具6. JVM的新特性7. 结论8. 参考资料

前言: Java 8 已经发布很久了,很多报道表明Java 8 是一次重大的版本升级。在Java Code Geeks上已经有很多介绍Java 8新特性的文章,...

1124
来自专栏jeremy的技术点滴

写py2、py3兼容的代码

8858
来自专栏java一日一条

关于Java集合的小抄

在尽可能短的篇幅里,将所有集合与并发集合的特征,实现方式,性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。

701
来自专栏蘑菇先生的技术笔记

探索c#之不可变数据类型

2064
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

1242
来自专栏写代码的海盗

scala与java之间的那些事

  scala与java之间的关系,我认为可以用一句话来开头:scala来源于java,但又高于java。   scala的设计者Martin Odersky就...

3675
来自专栏积累沉淀

【译】Java 8的新特性—终极版

声明:本文翻译自Java 8 Features Tutorial – The ULTIMATE Guide,翻译过程中发现并发编程网已经有同学翻译过了:...

24410
来自专栏androidBlog

Android 常用正则表达式

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/de...

1921
来自专栏搜云库

BTA 常问的 Java基础40道常见面试题及详细答案

最近看到网上流传着,各种面试经验及面试题,往往都是一大堆技术题目贴上去,而没有答案。

5926
来自专栏Netkiller

Solidity 智能合约开发语言·数据类型

中国广东省深圳市龙华新区民治街道溪山美地 518131 +86 13113668890 <netkiller@msn.com>

76310

扫码关注云+社区

领取腾讯云代金券