Dynamic Rankings
Time Limit: 10 Seconds
Memory Limit: 32768 KB
The Company Dynamic Rankings has developed a new kind of computer that is no
longer satisfied with the query like to simply find the k-th smallest number
of the given N numbers. They have developed a more powerful system such that
for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest
number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that
you have given to it). More powerful, you can even change the value of some
a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions
include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change
some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number
of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers
and M instruction. It is followed by N lines. The (i+1)-th line represents the
number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change
some a[i] to t, respectively. It is guaranteed that at any time of the operation.
Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There're NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e.
the k-th smallest number of a[i], a[i+1],..., a[j])
There're NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
-----------------------------------------------------------------------------------------------------------------------------
題目意思是要對(duì)一個(gè)序列詢問(wèn)某段當(dāng)中的第k大數(shù)，并且支持修改單個(gè)元素的操作。
50000的數(shù)據(jù)范圍顯然要我們用高級(jí)數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)，但是很囧的問(wèn)題就是：詢問(wèn)區(qū)間要用線段樹，詢問(wèn)第k大要用平衡樹。。。
解決這個(gè)問(wèn)題的方法很簡(jiǎn)單，就是線段樹套平衡樹，線段樹中的每個(gè)節(jié)點(diǎn)都有一棵平衡樹，維護(hù)線段樹所記錄的這個(gè)區(qū)間的元素。
這樣處理空間上是O(nlogn)的，因?yàn)榫€段樹有l(wèi)ogn層，每層的平衡樹所記的節(jié)點(diǎn)總數(shù)都有n個(gè)。
修改很容易想到，把所有包含要修改點(diǎn)的區(qū)間的平衡樹都修改了就行了，但查詢的時(shí)候又被囧到了：詢問(wèn)的區(qū)間不一定就是線段樹里面某個(gè)節(jié)點(diǎn)記的某個(gè)區(qū)間。
。。最終還是去找了hyf神牛。。。他一語(yǔ)點(diǎn)破天機(jī)：二分答案。。
對(duì)于每次查詢，二分第k大的數(shù)是多少，在線段樹里查詢這個(gè)區(qū)間中小于等于這個(gè)值的有多少個(gè)，就可以得到答案了。
需要注意的細(xì)節(jié)是：對(duì)于一個(gè)數(shù)，可能會(huì)有重復(fù)，比如對(duì)于1 2 2 2 3，查詢第2大的數(shù)，當(dāng)而分到2的時(shí)候，可能查到的是第三個(gè)2，查詢結(jié)果也就是4。為了解決這個(gè)問(wèn)題，可以在當(dāng)查詢不大于x的數(shù)的個(gè)數(shù)t1時(shí)，再查詢不大于x-1的數(shù)的個(gè)數(shù)t2，如果t2<k<=t1那么此時(shí)的x便是所求的第k大的數(shù)。
這樣的話，查詢是O(log(n)log(n)*log(MAXNUM)) (其實(shí)在查詢線段樹和平衡樹的時(shí)候不可能同時(shí)都達(dá)到log(n)，只是具體是多少我就算不來(lái)了。。望高手解答。。)，修改是O(log(n)*log(n))的(問(wèn)題同上。。)，就可以在時(shí)間范圍內(nèi)解決了。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #define MAXTREAPNODE 5000000
6 #define MAXLSTNODE 1000000
7 #define MAXN 50000
8 #define MAXNUM 1000000000
9 #define INFINIT 1000000000
10 using namespace std;
11
12
13 int a[MAXN+1];
14 class TreapNode{
15 public:
16 int v,lt,rt,p,size;
17 void set(int v){
18 this->v = v;
19 lt = rt = 0;
20 p = rand();
21 size = 1;
22 }
23 };
24 TreapNode treapnode[MAXTREAPNODE+1];
25 int pos = 0;
26 class Treap{
27 private:
28 int cnt,root;
29 void RightRotate(int &x){
30 int lc = treapnode[x].lt;
31 treapnode[x].lt = treapnode[lc].rt;
32 treapnode[lc].rt = x;
33 x = lc;
34 }
35 void LeftRotate(int &x){
36 int rc = treapnode[x].rt;
37 treapnode[x].rt = treapnode[rc].lt;
38 treapnode[rc].lt = x;
39 x = rc;
40 }
41 void Renew(int x){
42 if (!x) return;
43 treapnode[x].size = treapnode[treapnode[x].lt].size+treapnode[treapnode[x].rt].size+1;
44 }
45 void Add(int &x,int v){
46 if (!x) treapnode[x = (++pos)].set(v);
47 else{
48 if (v<=treapnode[x].v){
49 Add(treapnode[x].lt,v);
50 if (treapnode[treapnode[x].lt].p<treapnode[x].p)
51 RightRotate(x);
52 }
53 else if (v>treapnode[x].v){
54 Add(treapnode[x].rt,v);
55 if (treapnode[treapnode[x].rt].p<treapnode[x].p)
56 LeftRotate(x);
57 }
58 Renew(treapnode[x].lt),Renew(treapnode[x].rt),Renew(x);
59 }
60 }
61 void dfs(int x){
62 if (!x) return;
63 dfs(treapnode[x].lt);
64 printf("%d ",treapnode[x].v);
65 dfs(treapnode[x].rt);
66 }
67 int Ask(int &x,int k){
68 if (k<=treapnode[treapnode[x].lt].size) return Ask(treapnode[x].lt,k);
69 if (k == treapnode[treapnode[x].lt].size+1) return treapnode[x].v;
70 if (k>treapnode[treapnode[x].lt].size+1) return Ask(treapnode[x].rt,k-treapnode[treapnode[x].lt].size-1);
71 }
72 int Find(int &x,int v){
73 if (v == treapnode[x].v) return treapnode[treapnode[x].lt].size+1;
74 if (v<treapnode[x].v){
75 return Find(treapnode[x].lt,v);
76 }
77 if (v>treapnode[x].v){
78 return treapnode[treapnode[x].lt].size+1+Find(treapnode[x].rt,v);
79 }
80 }
81 void Del(int &x,int v){
82 if (v<treapnode[x].v) Del(treapnode[x].lt,v);
83 else if (v>treapnode[x].v) Del(treapnode[x].rt,v);
84 else{
85 if (!treapnode[x].lt&&!treapnode[x].rt)
86 x = 0;
87 else if (treapnode[x].lt&&!treapnode[x].rt)
88 x = treapnode[x].lt;
89 else if (!treapnode[x].lt&&treapnode[x].rt)
90 x = treapnode[x].rt;
91 else if (treapnode[treapnode[x].lt].p<treapnode[treapnode[x].rt].p)
92 RightRotate(x),Del(treapnode[x].rt,v);
93 else
94 LeftRotate(x),Del(treapnode[x].lt,v);
95 }
96 Renew(treapnode[x].lt),Renew(treapnode[x].rt),Renew(x);
97 }
98 int GetSmaller(int x,int v){
99 if (!x) return 0;
100 if (treapnode[x].v<=v)
101 return treapnode[treapnode[x].lt].size+1+GetSmaller(treapnode[x].rt,v);
102 if (treapnode[x].v>v) return GetSmaller(treapnode[x].lt,v);
103 }
104 public:
105 Treap(){cnt = root = 0;}
106 void Add(int v){
107 cnt++;
108 Add(root,v);
109 }
110 void dfs(){
111 dfs(root);
112 }
113 int Ask(int k){
114 return Ask(root,k);
115 }
116 int Find(int v){
117 return Find(root,v);
118 }
119 void Change(int v1,int v2){
120 Del(v1);
121 Add(v2);
122 }
123 void Del(int v){
124 cnt--;
125 Del(root,v);
126 }
127 void DelRank(int k){
128 int v = Ask(k);
129 Del(v);
130 }
131 int Amount(){return cnt;}
132 void Clear(){cnt = root = 0;}
133 int GetSmaller(int x){
134 return GetSmaller(root,x);
135 }
136 };
137 class LSTNode{
138 public:
139 int l,r,lt,rt;
140 Treap T;
141 };
142 int tot = 0;
143 LSTNode lstnode[MAXLSTNODE+1];
144 class LST{
145 private:
146 int AskRank(int x,int l,int r,int v){
147 if (lstnode[x].l>=l&&lstnode[x].r<=r)
148 return lstnode[x].T.GetSmaller(v);
149 else{
150 int mid = (lstnode[x].l+lstnode[x].r)>>1;
151 if (r<=mid) return AskRank(lstnode[x].lt,l,r,v);
152 else if (l>mid) return AskRank(lstnode[x].rt,l,r,v);
153 else
154 return AskRank(lstnode[x].lt,l,r,v)+AskRank(lstnode[x].rt,l,r,v);
155 }
156 }
157 void Modify(int x,int p,int v){
158 lstnode[x].T.Change(a[p],v);
159 if (lstnode[x].l == lstnode[x].r) return;
160 int mid = (lstnode[x].l+lstnode[x].r)>>1;
161 if (p<=mid) Modify(lstnode[x].lt,p,v);
162 else if (p>mid) Modify(lstnode[x].rt,p,v);
163 else{
164 Modify(lstnode[x].lt,p,v);
165 Modify(lstnode[x].rt,p,v);
166 }
167 }
168 public:
169 LST(){tot=0;pos = 0;}
170 void BuildTree(int l,int r){
171 int x = ++tot;
172 lstnode[x].T.Clear();
173 lstnode[x].l = l,lstnode[x].r = r;
174 for (int i = l; i<=r; i++)
175 lstnode[x].T.Add(a[i]);
176 if (l == r) lstnode[x].lt = lstnode[x].rt = 0;
177 else{
178 int mid = (l+r)>>1;
179 lstnode[x].lt = tot+1,BuildTree(l,mid);
180 lstnode[x].rt = tot+1,BuildTree(mid+1,r);
181 }
182 }
183 int Ask(int L,int R,int k){
184 int l = 0,r = MAXNUM;
185 while (l<=r){
186 int mid = (l+r)>>1;
187 int t1 = AskRank(1,L,R,mid);
188 int t2 = AskRank(1,L,R,mid-1);
189 if (k<=t1&&k>t2) return mid;
190 if (t1<k) l = mid+1;
191 else r = mid;
192 }
193 }
194 void Modify(int p,int v){
195 Modify(1,p,v);
196 a[p] = v;
197 }
198 void Clear(){
199 tot = 0;pos = 0;
200 }
201 };
202 LST T;
203 void Solve(){
204 T.Clear();
205 int n,m;
206 scanf("%d%d",&n,&m);
207 for (int i = 1; i<=n; i++)
208 scanf("%d",&a[i]);
209 T.BuildTree(1,n);
210 for (int i = 1; i<=m; i++){
211 char ch;
212 int t1,t2,t3;
213 scanf("%c",&ch);
214 while (ch == '\n'||ch == ' ') scanf("%c",&ch);
215 if (ch == 'Q'){
216 scanf("%d%d%d",&t1,&t2,&t3);
217 printf("%d\n",T.Ask(t1,t2,t3));
218 }
219 if (ch == 'C'){
220 scanf("%d%d",&t1,&t2);
221 T.Modify(t1,t2);
222 }
223 }
224 }
225 int main(){
226 //freopen("2112.in","r",stdin);
227 //freopen("2112.out","w",stdout);
228 srand(1);
229 int t;
230 scanf("%d",&t);
231 while (t--)
232 Solve();
233 return 0;
234 }
235