hdu 2665 （poj 2104） 划分树
poj2104题目要求弱一些，n个数是不同的。hdu2665中没有这样的限制。所以在划分左右区间时需要处理一下相同的数怎么划分。
#include<stdio.h>#include<algorithm>#include<string.h>#define M 100010using namespace std;int tr[20][M],num[20][M],sorted[M];void build(int l,int r,int d){ if(l==r) return ; int m=(l+r)/2; int lp=l,rp=m+1; int h=1; for(int j=m-1;j>=l;j--) { if( sorted[j]==sorted[m] ) h++; else break; } for(int i=l;i<=r;i++) { num[d][i]=num[d][i-1]; if( tr[d][i]<sorted[m] && lp<=m) { tr[d+1][lp++]=tr[d][i]; num[d][i]++; } else if( tr[d][i]==sorted[m]) { if( h>0 ) { tr[d+1][lp++]=tr[d][i],h--; num[d][i]++; } else tr[d+1][rp++]=tr[d][i]; } else { tr[d+1][rp++]=tr[d][i]; } } build(l,m,d+1); build(m+1,r,d+1);}int query(int s,int t,int k,int l,int r,int d){ int m=(l+r)/2; if(s==t) return tr[d][s]; int p=num[d][t]-num[d][s-1]; int sl=num[d][s-1]-num[d][l-1]; if( p>=k ) { return query(l+sl,l+sl+p-1,k,l,m,d+1); } else { int b=s-l-sl; int bb=t-s+1-p; return query( m+b+1,m+b+bb,k-p,m+1,r,d+1); }}int main(){ int n,m,i,j,k,s,t,T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); memset(num,0,sizeof(num)); memset(tr,0,sizeof(tr)); for(i=1;i<=n;i++) { scanf("%d",&sorted[i]); tr[0][i]=sorted[i]; } sort(sorted+1,sorted+n+1); build(1,n,0); for(i=1;i<=m;i++) { scanf("%d%d%d",&s,&t,&k); int ans=query(s,t,k,1,n,0); printf("%d\n",ans); } } return 0;}