|
|
题目链接：http://poj.org/problem?id=2104
  /**//*
 题意：
给出一个长度为N(N <= 100000)的数列，然后是一连串询问，询问数
<= 50000，询问的格式是a, b, k，问[a, b]区间中的k小数。
解法：
二分+归并树+线段树
思路：
看到这道题就会让我想起大一的时光，又会油然而生疯狂做题的冲动，
那时候参加了武汉的全国邀请赛，其中有道题就是求区间K大数，可惜我们
队都没怎么接触过线段树，所以都不会。回来之后也一直想不出怎么做，一
直都搁置在那里，直到第二年的寒假才想到做法。
其实学完线段树后也不难想到，而且是个经典的不能再经典的算法。首
先是建立一颗归并树，所谓归并树就是在树的每个结点管理的区间内的元素
都是单调的，和线段树一样，它同样也是一颗完全二叉树。那么我们在建树
的时候利用当前子树的左右儿子的归并数组递归完成每一层的建树过程，最
后就是一颗每一个结点都有序的归并树。在每次询问区间[a,b]时，将[a,b]
利用线段树划分成每一段都有序的小区间，这样一来就可以通过二分枚举答
案，然后再通过二分查找在每一段小区间内统计小于等于当前答案的数的个
数，和K进行比较，最后得到答案。
 */
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
int n, m;
int val[maxn], sor[maxn];
int Tree[31][maxn];
struct Pair  {
int idx, l, r;
int len;
  Pair() {}
Pair(int _idx, int _l, int _r) {
idx = _idx;
l = _l;
r = _r;
len = r - l + 1;
 }
};
Pair Pa[1000];
bool cmp(Pair a, Pair b) {
return a.len > b.len;
}
int PaSize;
void Merge(int dep, int l, int r) {
int mid = (l + r) >> 1;
int pos = 0;
int lidx = l;
int ridx = mid + 1;
while(l + pos <= r) {
if(lidx <= mid && ridx <= r) {
int& nidx = Tree[dep+1][lidx] < Tree[dep+1][ridx] ? lidx : ridx;
Tree[dep][l+(pos++)] = Tree[dep+1][nidx++];
}else {
if(lidx > mid) {
for(int i = ridx; i <= r; i++)
Tree[dep][l+(pos++)] = Tree[dep+1][i];
break;
}else {
for(int i = lidx; i <= mid; i++)
Tree[dep][l+(pos++)] = Tree[dep+1][i];
break;
}
}
}
}
void Build(int dep, int p, int l, int r) {
if(l == r) {
Tree[dep][l] = val[l];
return ;
}
int mid = (l + r) >> 1;
Build(dep+1, p<<1, l, mid);
Build(dep+1, p<<1|1, mid+1, r);
Merge(dep, l, r);
}
void Query(int dep, int p, int l, int r, int a, int b) {
if(l == a && b == r) {
Pa[ PaSize++ ] = Pair(dep, l, r);
return ;
}
int mid = (l + r) >> 1;
if(b <= mid)
Query(dep+1, p<<1, l, mid, a, b);
else if(mid + 1 <= a)
Query(dep+1, p<<1|1, mid+1, r, a, b);
else {
Query(dep+1, p<<1, l, mid, a, mid);
Query(dep+1, p<<1|1, mid+1, r, mid+1, b);
}
}
int LessEqualThan(int ID, int val) {
int l = Pa[ID].l;
int r = Pa[ID].r;
int ans = -1;
if(Tree[Pa[ID].idx][l] > val) return 0;
if(Tree[Pa[ID].idx][r] <= val) return r - l + 1;
while(l <= r) {
int m = (l + r) >> 1;
if(Tree[Pa[ID].idx][m] <= val) {
l = m + 1;
if(m > ans)
ans = m;
}else
r = m - 1;
}
return (ans == -1) ? 0 : (ans - Pa[ID].l + 1);
}
int KthNum(int l, int r, int K) {
PaSize = 0;
Query(0, 1, 1, n, l, r);
int i;
int low = 0;
int hig = n-1;
int ans = n-1;
sort(Pa, Pa + PaSize, cmp);
while(low <= hig) {
int m = (low + hig) >> 1;
int le = 0;
int v = sor[m];
for(i = 0; i < PaSize; i++) {
le += LessEqualThan(i, v);
if(le >= K)
break;
}
if(le >= K) {
hig = m - 1;
if(m < ans)
ans = m;
}else
low = m + 1;
}
return sor[ans];
}
int main() {
int i;
int t;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
sor[i-1] = val[i];
}
sort(sor, sor + n);
Build(0, 1, 1, n);
while(m--) {
int a, b, k;
scanf("%d %d %d", &a, &b, &k);
printf("%d\n", KthNum(a, b, k));
}
}
return 0;
}
|