划分树

划分树和归并树都是用线段树作为辅助的，原理是基于快排 和归并排序 的。

划分树的建树过程基本就是模拟快排过程，取一个已经排过序的区间中值，然后把小于中值的点放左边，大于的放右边。并且记录d层第i个数之前（包括i）小于中值的放在左边的数。具体看下面代码注释。

查找其实是关键，因为再因查找[l,r]需要到某一点的左右孩子时需要把[l,r]更新。具体分如下几种情况讨论：
假设要在区间[l,r]中查找第k大元素，t为当前节点，lch，rch为左右孩子，left，mid为节点t左边界和中间点。
1、sum[r]-sum[l-1]>=k，查找lch[t],区间对应为[ left+sum[l-1] , left+sum[r]-1 ]
2、sum[r]-sum[l-1]<k,查找rch[t]，区间对应为[ mid+1+l-left-sum[l-1] , mid+1+r-left-sum[r] ]

上面两个关系在纸上可以推出来，对着上图更容易理解关系式

模板如下poj2104:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define clr(x) memset(x,0,sizeof x)
#define rep(i,a,b) for (int i=a;i<=b;++i)
using namespace std;
int T[20][N],sum[20][N],n,m,a[N];
void build(int c,int l,int r) {
	int mid=(l+r)>>1,lp=l,rp=mid+1,lm=mid-l+1;
	rep(i,l,r) lm-=(a[i]<a[mid]);
	rep(i,l,r) {
		sum[c][i]=(i==l)?0:sum[c][i-1];
		if (T[c][i]==a[mid]) {
			if (lm) --lm,sum[c][i]++,T[c+1][lp++]=T[c][i];
			else T[c+1][rp++]=T[c][i];
		} else if (T[c][i]<a[mid]) sum[c][i]++,T[c+1][lp++]=T[c][i];
		else T[c+1][rp++]=T[c][i];
	}
	if (l==r) return;
	build(c+1,l,mid),build(c+1,mid+1,r);
}
int query(int c,int l,int r,int lp,int rp,int k) {
	if (l==r) return T[c][l];
	int mid=(l+r)>>1,s=(l==lp)?0:sum[c][lp-1],ss=sum[c][rp]-s;
	return (k<=ss)?query(c+1,l,mid,l+s,l+s+ss-1,k):query(c+1,mid+1,r,lp-l-s+1+mid,rp-l+1-s-ss+mid,k-ss);
}
int main() {
	while (~scanf("%d%d",&n,&m)) {
		rep(i,1,n) scanf("%d",&a[i]),T[0][i]=a[i];
		sort(a+1,a+n+1); build(0,1,n);
		while (m--) {
			int lp,rp,k;scanf("%d%d%d",&lp,&rp,&k);
			printf("%d\n",query(0,1,n,lp,rp,k));
		}
	}
	return 0;
}