2012-08-24 11:35:58Morris
[ZJ][歸併樹] a331. K-th Number
內容 ：
You are working for
Macrohard company in data structures department. After failing your
previous task about key insertion you were asked to write a new data
structure that would be able to return quickly k-th order statistics in
the array segment.
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.
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.
輸入說明
：
The first line of the
input file contains n --- the size of the array, and m --- the number
of questions to answer (1 <= n <= 100 000, 1 <= m <= 5
000).
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).
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).
輸出說明
：
For each question output the answer to it --- the k-th number in sorted a[i...j] segment.
範例輸入 ：
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
範例輸出 ：
5 6 3
提示
：
出處
：
Northeastern Europe 2004, Northern Subregion
(管理：david942j)
轉載 http://hi.baidu.com/zhiqing110c/item/9cd539fa1d0127693c148556
1，建立归并树后我们得到了序列key[]的非降序排列，由于此时key[]内元素的rank是非递减的，因此key[]中属于指定区间[s,t]内的元 素的rank也是非递减的，所以我们可以用二分法枚举key[]中的元素并求得它在[s,t]中的 rank值，直到该rank值和询问中的rank值相等；
2，那对于key[]中的某个元素val，如何求得它在指定区间[s,t]中的 rank？这就要利用到刚建好的归并树：我们可以利用类似线段树的 query[s,t]操作找到所有属于[s,t]的子区间，然后累加val分别在这些子区间内的rank，得到的就是val在区间[s,t]中的 rank，注意到这和合并排序的合并过程一致；
3，由于属于子区间的元素的排序结果已经记录下来，所以val在子区间内的rank可以通过二分法得到。
上面三步经过了三次二分操作（query也是种二分），于是每次询问的复杂度是O(log n * log n * log n)
#include <stdio.h>
typedef struct {
int l, r;
} Node;
Node ST[262145];
int seg[20][100005];
int a[100005];
void build(int l, int r, int k, int depth) {
ST[k].l = l, ST[k].r = r;
if(l == r) {
seg[depth][l] = a[l];
return;
}
int m = (l+r)>>1;
build(l, m, k<<1, depth+1);
build(m+1, r, k<<1|1, depth+1);
int idx1 = l, idx2 = m+1, top = l;
while(idx1 <= m && idx2 <= r) {
if(seg[depth+1][idx1] < seg[depth+1][idx2])
seg[depth][top++] = seg[depth+1][idx1++];
else
seg[depth][top++] = seg[depth+1][idx2++];
}
while(idx1 <= m) seg[depth][top++] = seg[depth+1][idx1++];
while(idx2 <= r) seg[depth][top++] = seg[depth+1][idx2++];
}
int find(int k, int dep, int val, int ql, int qr) {
if(ql <= ST[k].l && ST[k].r <= qr) {
int l = ST[k].l, r = ST[k].r;
while(l < r) {
int m = (l+r)>>1;
if(seg[dep][m] < val)
l = m+1;
else
r = m;
}
if(seg[dep][l] <= val)
return l - ST[k].l+1;
else
return l - ST[k].l;
}
int res = 0;
if(ql <= ST[k<<1].r)
res += find(k<<1, dep+1, val, ql, qr);
if(qr >= ST[k<<1|1].l)
res += find(k<<1|1, dep+1, val, ql, qr);
return res;
}
int main() {
int n, m, ql, qr, k, i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, n, 1, 1);
while(m--) {
scanf("%d %d %d", &ql, &qr, &k);
int l = 1, r = n;
while(l < r) {
int m = (l+r)>>1;
if(find(1, 1, seg[1][m], ql, qr) < k)
l = m+1;
else
r = m;
}
printf("%d\n", seg[1][l]);
}
}
return 0;
}
轉載 http://hi.baidu.com/zhiqing110c/item/9cd539fa1d0127693c148556
1，建立归并树后我们得到了序列key[]的非降序排列，由于此时key[]内元素的rank是非递减的，因此key[]中属于指定区间[s,t]内的元 素的rank也是非递减的，所以我们可以用二分法枚举key[]中的元素并求得它在[s,t]中的 rank值，直到该rank值和询问中的rank值相等；
2，那对于key[]中的某个元素val，如何求得它在指定区间[s,t]中的 rank？这就要利用到刚建好的归并树：我们可以利用类似线段树的 query[s,t]操作找到所有属于[s,t]的子区间，然后累加val分别在这些子区间内的rank，得到的就是val在区间[s,t]中的 rank，注意到这和合并排序的合并过程一致；
3，由于属于子区间的元素的排序结果已经记录下来，所以val在子区间内的rank可以通过二分法得到。
上面三步经过了三次二分操作（query也是种二分），于是每次询问的复杂度是O(log n * log n * log n)
#include <stdio.h>
typedef struct {
int l, r;
} Node;
Node ST[262145];
int seg[20][100005];
int a[100005];
void build(int l, int r, int k, int depth) {
ST[k].l = l, ST[k].r = r;
if(l == r) {
seg[depth][l] = a[l];
return;
}
int m = (l+r)>>1;
build(l, m, k<<1, depth+1);
build(m+1, r, k<<1|1, depth+1);
int idx1 = l, idx2 = m+1, top = l;
while(idx1 <= m && idx2 <= r) {
if(seg[depth+1][idx1] < seg[depth+1][idx2])
seg[depth][top++] = seg[depth+1][idx1++];
else
seg[depth][top++] = seg[depth+1][idx2++];
}
while(idx1 <= m) seg[depth][top++] = seg[depth+1][idx1++];
while(idx2 <= r) seg[depth][top++] = seg[depth+1][idx2++];
}
int find(int k, int dep, int val, int ql, int qr) {
if(ql <= ST[k].l && ST[k].r <= qr) {
int l = ST[k].l, r = ST[k].r;
while(l < r) {
int m = (l+r)>>1;
if(seg[dep][m] < val)
l = m+1;
else
r = m;
}
if(seg[dep][l] <= val)
return l - ST[k].l+1;
else
return l - ST[k].l;
}
int res = 0;
if(ql <= ST[k<<1].r)
res += find(k<<1, dep+1, val, ql, qr);
if(qr >= ST[k<<1|1].l)
res += find(k<<1|1, dep+1, val, ql, qr);
return res;
}
int main() {
int n, m, ql, qr, k, i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, n, 1, 1);
while(m--) {
scanf("%d %d %d", &ql, &qr, &k);
int l = 1, r = n;
while(l < r) {
int m = (l+r)>>1;
if(find(1, 1, seg[1][m], ql, qr) < k)
l = m+1;
else
r = m;
}
printf("%d\n", seg[1][l]);
}
}
return 0;
}