|
|
題目鏈接：http://poj.org/problem?id=2104
  /**//*
 題意：
給出一個長度為N(N <= 100000)的數(shù)列，然后是一連串詢問，詢問數(shù)
<= 50000，詢問的格式是a, b, k，問[a, b]區(qū)間中的k小數(shù)。
解法：
二分+歸并樹+線段樹
思路：
看到這道題就會讓我想起大一的時光，又會油然而生瘋狂做題的沖動，
那時候參加了武漢的全國邀請賽，其中有道題就是求區(qū)間K大數(shù)，可惜我們
隊都沒怎么接觸過線段樹，所以都不會。回來之后也一直想不出怎么做，一
直都擱置在那里，直到第二年的寒假才想到做法。
其實學(xué)完線段樹后也不難想到，而且是個經(jīng)典的不能再經(jīng)典的算法。首
先是建立一顆歸并樹，所謂歸并樹就是在樹的每個結(jié)點管理的區(qū)間內(nèi)的元素
都是單調(diào)的，和線段樹一樣，它同樣也是一顆完全二叉樹。那么我們在建樹
的時候利用當前子樹的左右兒子的歸并數(shù)組遞歸完成每一層的建樹過程，最
后就是一顆每一個結(jié)點都有序的歸并樹。在每次詢問區(qū)間[a,b]時，將[a,b]
利用線段樹劃分成每一段都有序的小區(qū)間，這樣一來就可以通過二分枚舉答
案，然后再通過二分查找在每一段小區(qū)間內(nèi)統(tǒng)計小于等于當前答案的數(shù)的個
數(shù)，和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;
}
|