# 1901: Zju2112 Dynamic Rankings

## 1901: Zju2112 Dynamic Rankings

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 5268  Solved: 2207

[Submit][Status][Discuss]

## Sample Input

5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3

3 6

## HINT

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

## Source

```  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
188         built(1,1,n);
189         for i:=1 to n do
190                 begin
192                         putin(i,j);
193                 end;
195         for i:=1 to m do
196                 begin
198                         case upcase(ch) of
199                                 'Q':begin
201                                         writeln(rankget(j,k,l));
202                                 end;
203                                 'C':begin
205                                         change(j,k);
206                                 end;
207                         end;
208
209                 end;
210 end.```

0 条评论

• ### 2761: [JLOI2011]不重复数字（平衡树）

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

• ### 1050: [HAOI2006]旅行comf

1050: [HAOI2006]旅行comf Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1495  So...

• ### 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

• ### 2761: [JLOI2011]不重复数字（平衡树）

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

• ### 1050: [HAOI2006]旅行comf

1050: [HAOI2006]旅行comf Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1495  So...

• ### 算法模板——平衡树Treap 2

实现功能：同平衡树Treap 1（BZOJ3224 / tyvj1728） 这次的模板有了不少的改进，显然更加美观了，几乎每个部分都有了不少简化，尤其是删除部分...

• ### 算法模板——线段树8 （字符串回文变换）

实现功能：输入一个长度为N的由26个大写字母组成的字符串，输入M条指令："1 x y"，将x到y的字串重组构成一个字典序最小的回文串，如果不能构成回文串输出Fa...

• ### DTcms4/5远程图片自动保存报错：A generic error occurred in GDI+.

玩了很久DTcms，今天居然在保存远程图片到本地时，报了错误：A generic error occurred in GDI+.