首页 > 代码库 > ZOJ 2112 Dynamic Rankings（主席树の动态kth）
ZOJ 2112 Dynamic Rankings（主席树の动态kth）
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112
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.
题目大意：给n个数，有m个操作。修改某个数，或者询问一段区间的第k小值。
思路：首先要知道没有修改操作的区间第k大怎么用出席树写：POJ 2104 K-th Number（主席树——附讲解）
至于动态kth的解法可以去看CLJ的《可持久化数据结构研究》（反正我是看这个才懂的），然后在网上查一些资料，YY一下就可以了。
这里写的是树状数组套线段树+可持久化线段树的做法（因为内存不够用）。
简单的讲就是通过树状数组求和，维护前k个线段树的和。时间复杂度为O(nlogn+m(logn)^2)
另参考资料（里面有好几个link :)）：http://www.cnblogs.com/kuangbin/p/3308118.html
PS：ZOJ的指针似乎不是4个字节的。这里用指针就要MLE了（代码本来不是这么丑的啊T_T）。
代码（130MS）：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXN = 50010; 9 const int MAXM = 10010; 10 const int MAXT = MAXM * 15 * 16; 11 12 struct Query { 13 char op; 14 int i, j, k; 15 void read() { 16 scanf(" %c", &op); 17 if(op == ‘Q‘) scanf("%d%d%d", &i, &j, &k); 18 else scanf("%d%d", &i, &k); 19 } 20 } query[MAXM]; 21 int a[MAXN]; 22 int n, m, T; 23 //hashmap 24 int arr[MAXN + MAXM], total; 25 26 void buildHash() { 27 total = 0; 28 for(int i = 1; i <= n; ++i) arr[total++] = a[i]; 29 for(int i = 1; i <= m; ++i) 30 if(query[i].op == ‘C‘) arr[total++] = query[i].k; 31 sort(arr, arr + total); 32 total = unique(arr, arr + total) - arr; 33 } 34 35 int hash(int x) { 36 return lower_bound(arr, arr + total, x) - arr; 37 } 38 //Chairman tree 39 struct Node { 40 int lson, rson, sum; 41 void clear() { 42 lson = rson = sum = 0; 43 } 44 } tree[MAXT]; 45 int root[MAXN]; 46 int tcnt; 47 48 void insert(int& rt, int l, int r, int pos) { 49 tree[tcnt] = tree[rt]; rt = tcnt++; 50 tree[rt].sum++; 51 if(l < r) { 52 int mid = (l + r) >> 1; 53 if(pos <= mid) insert(tree[rt].lson, l, mid, pos); 54 else insert(tree[rt].rson, mid + 1, r, pos); 55 } 56 } 57 58 void buildTree() { 59 tcnt = 1; 60 for(int i = 1; i <= n; ++i) { 61 root[i] = root[i - 1]; 62 insert(root[i], 0, total - 1, hash(a[i])); 63 } 64 } 65 //Binary Indexed Trees 66 int root2[MAXN]; 67 int roota[50], rootb[50]; 68 int cnta, cntb; 69 70 void initBIT() { 71 for(int i = 1; i <= n; ++i) root2[i] = 0; 72 } 73 74 inline int lowbit(int x) { 75 return x & -x; 76 } 77 78 void insert(int& rt, int l, int r, int pos, int val) { 79 if(rt == 0) tree[rt = tcnt++].clear(); 80 if(l == r) { 81 tree[rt].sum += val; 82 } else { 83 int mid = (l + r) >> 1; 84 if(pos <= mid) insert(tree[rt].lson, l, mid, pos, val); 85 else insert(tree[rt].rson, mid + 1, r, pos, val); 86 tree[rt].sum = tree[tree[rt].lson].sum + tree[tree[rt].rson].sum; 87 } 88 } 89 90 int kth(int ra, int rb, int l, int r, int k) { 91 if(l == r) { 92 return l; 93 } else { 94 int sum = tree[tree[rb].lson].sum - tree[tree[ra].lson].sum, mid = (l + r) >> 1; 95 for(int i = 0; i < cntb; ++i) sum += tree[tree[rootb[i]].lson].sum; 96 for(int i = 0; i < cnta; ++i) sum -= tree[tree[roota[i]].lson].sum; 97 if(sum >= k) { 98 for(int i = 0; i < cntb; ++i) rootb[i] = tree[rootb[i]].lson; 99 for(int i = 0; i < cnta; ++i) roota[i] = tree[roota[i]].lson;100 return kth(tree[ra].lson, tree[rb].lson, l, mid, k);101 } else {102 for(int i = 0; i < cntb; ++i) rootb[i] = tree[rootb[i]].rson;103 for(int i = 0; i < cnta; ++i) roota[i] = tree[roota[i]].rson;104 return kth(tree[ra].rson, tree[rb].rson, mid + 1, r, k - sum);105 }106 }107 }108 //Main operation109 void modify(int k, int val) {110 int x = hash(a[k]), y = hash(val);111 a[k] = val;112 while(k <= n) {113 insert(root2[k], 0, total - 1, x, -1);114 insert(root2[k], 0, total - 1, y, 1);115 k += lowbit(k);116 }117 }118 119 int kth(int l, int r, int k) {120 cnta = cntb = 0;121 for(int i = l - 1; i; i -= lowbit(i)) roota[cnta++] = root2[i];122 for(int i = r; i; i -= lowbit(i)) rootb[cntb++] = root2[i];123 return kth(root[l - 1], root[r], 0, total - 1, k);124 }125 126 int main() {127 scanf("%d", &T);128 while(T--) {129 scanf("%d%d", &n, &m);130 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);131 for(int i = 1; i <= m; ++i) query[i].read();132 buildHash();133 buildTree();134 initBIT();135 for(int i = 1; i <= m; ++i) {136 if(query[i].op == ‘Q‘) printf("%d\n", arr[kth(query[i].i, query[i].j, query[i].k)]);137 else modify(query[i].i, query[i].k);138 }139 }140 }