2015 Multi-University Training Contest 10 hdu 5412 CRB and Queries

CRB and Queries

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 533 Accepted Submission(s): 125

Problem Description
There are N boys in CodeLand.
Boy i has his coding skill Ai.
CRB wants to know who has the suitable coding skill.
So you should treat the following two types of queries.
Query 1: 1 l v
The coding skill of Boy l has changed to v.
Query 2: 2 l r k
This is a report query which asks the k-th smallest value of coding skill between Boy l and Boy r(both inclusive).

Input
There are multiple test cases.
The first line contains a single integer N.
Next line contains N space separated integers A1, A2, …, AN, where Ai denotes initial coding skill of Boy i.
Next line contains a single integer Q representing the number of queries.
Next Q lines contain queries which can be any of the two types.
1 ≤ N, Q ≤ 105
1 ≤ Ai, v ≤ 109
1 ≤ l ≤ r ≤ N
1 ≤ k ≤ r – l + 1

Output
For each query of type 2, output a single integer corresponding to the answer in a single line.

Sample Input
5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2

Sample Output
3
4

Author
KUT（DPRK）

Source

2015 Multi-University Training Contest 10 1007

解题：带修改的区间K大查询

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 300010;
 4 const int INF = 0x3f3f3f3f;
 5 struct QU {
 6     int x,y,k,id,d;
 7 } Q[maxn],A[maxn],B[maxn];
 8 int a[maxn],c[maxn],ans[maxn],tot;
 9 void add(int i,int val) {
10     while(i < maxn) {
11         c[i] += val;
12         i += i&-i;
13     }
14 }
15 int sum(int i,int ret = 0) {
16     while(i > 0) {
17         ret += c[i];
18         i -= i&-i;
19     }
20     return ret;
21 }
22 void solve(int lt,int rt,int L,int R) {
23     if(lt > rt) return;
24     if(L == R) {
25         for(int i = lt; i <= rt; ++i)
26             if(Q[i].id) ans[Q[i].id] = L;
27         return;
28     }
29     int mid = (L + R)>>1,a = 0,b = 0;
30     for(int i = lt; i <= rt; ++i) {
31         if(Q[i].id) {
32             int tmp = sum(Q[i].y) - sum(Q[i].x-1);
33             if(Q[i].d + tmp >= Q[i].k) A[a++] = Q[i];
34             else {
35                 Q[i].d += tmp;
36                 B[b++] = Q[i];
37             }
38         } else if(Q[i].y <= mid) {
39             add(Q[i].x,Q[i].d);
40             A[a++] = Q[i];
41         } else B[b++] = Q[i];
42     }
43     for(int i = lt; i <= rt; ++i)
44         if(!Q[i].id && Q[i].y <= mid) add(Q[i].x,-Q[i].d);
45     for(int i = 0; i < a; ++i) Q[lt + i] = A[i];
46     for(int i = 0; i < b; ++i) Q[lt + a + i] = B[i];
47     solve(lt,lt + a - 1,L,mid);
48     solve(lt + a,rt,mid + 1,R);
49 }
50 int main() {
51     int n,m,cnt,x,y;
52     while(~scanf("%d",&n)) {
53         memset(c,0,sizeof c);
54         cnt = tot = 0;
55         for(int i = 1; i <= n; ++i) {
56             scanf("%d",a + i);
57             Q[++tot].y = a[i];
58             Q[tot].x = i;
59             Q[tot].id = 0;
60             Q[tot].d = 1;
61         }
62         scanf("%d",&m);
63         for(int i = 1,op; i <= m; ++i) {
64             scanf("%d",&op);
65             if(op == 2) {
66                 tot++;
67                 scanf("%d%d%d",&Q[tot].x,&Q[tot].y,&Q[tot].k);
68                 Q[tot].id = ++cnt;
69                 Q[tot].d = 0;
70             } else {
71                 scanf("%d%d",&x,&y);
72                 Q[++tot].x = x;
73                 Q[tot].y = a[x];
74                 Q[tot].id = 0;
75                 Q[tot].d = -1;
76 
77                 Q[++tot].x = x;
78                 Q[tot].y = a[x] = y;
79                 Q[tot].id = 0;
80                 Q[tot].d = 1;
81             }
82         }
83         solve(1,tot,0,INF);
84         for(int i = 1; i <= cnt; ++i)
85             printf("%d
",ans[i]);
86     }
87     return 0;
88 }

View Code