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