|
|
題目鏈接：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;
}
|