[POJ 2104] K-th Number【莫队+树状数组】
Problem:
Time Limit: 20000MS | Memory Limit: 65536K | |
Case Time Limit: 2000MS |
Description
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
Input
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output
Sample Input
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
Sample Output
5 6 3
Hint
Source
Solution:
这道题我之前用归并树做过,参考 [POJ 2104] K-th Number【归并树】。
今天学了莫队算法,据说可以“处理一切区间问题”,就用莫队做了一下 ~~
这次的莫队要和树状数组分工合作。
首先要离散化。
在更新的同时,维护区间 [l, r] 中 ≤ i 的数的个数。
询问第 k 小时,我们在树状数组上二分下标 i,询问 ≤ i 的数的个数,直到 i == k。
关于莫队详见: [BZOJ 2038][国家集训队2009]小Z的袜子【莫队】。
Code: O(nlogn+n1.5+mn0.5+mlogm+mlog2n) [2332K, 2485MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; inline void getint(int &num){ char ch; int sgn = 1; while(!isdigit(ch = getchar())) if(ch == '-') sgn = -1; num = ch - '0'; while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0'; num *= sgn; } int n, m, a[100005], bl[100005]; int disc[100005], ans[5005]; struct Query{ int id, l, r, k; } q[5005]; inline bool cmp(const Query &q1, const Query &q2){ if(bl[q1.l] == bl[q2.l]) return q1.r < q2.r; return q1.l < q2.l; } struct BIT{ int node[100005]; inline void add(int u, int v) {while(u < n) node[u] += v, u += u & -u;} inline int query(int u) {int res = 0; while(u) res += node[u], u -= u & -u; return res;} inline int inv_rank(int k){ int l = 1, r = n; while(l < r){ int mid = l + r >> 1; if(query(mid) >= k) r = mid; else l = mid + 1; } return l; } } b; inline void update(int pos, int val) {b.add(a[pos], val);} inline void Mo(){ sort(q + 1, q + m + 1, cmp); for(register int i = 1, l = 1, r = 0; i <= m; i++){ while(r < q[i].r) update(++r, 1); while(r > q[i].r) update(r--, -1); while(l < q[i].l) update(l++, -1); while(l > q[i].l) update(--l, 1); ans[q[i].id] = disc[b.inv_rank(q[i].k)]; // Must take the original value } } int main(){ getint(n), getint(m); int blocksize = int(sqrt(n)); for(register int i = 1; i <= n; i++) bl[i] = (i - 1) / blocksize + 1; for(register int i = 1; i <= n; i++) getint(a[i]), disc[i] = a[i]; for(register int i = 1; i <= m; i++) getint(q[i].l), getint(q[i].r), getint(q[i].k), q[i].id = i; sort(disc + 1, disc + n + 1); int dsize = unique(disc + 1, disc + n + 1) - disc - 1; for(register int i = 1; i <= n; i++) a[i] = lower_bound(disc + 1, disc + dsize + 1, a[i]) - disc; // Discretization Mo(); for(register int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }
发表评论