hdu 4417 2012杭州网络赛 划分树
划分树，对区间进行二分求 第mid 大的数 并且和 H比较即可。。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 100010#define lson u<<1#define rson u<<1|1int sorted[MAXN],val[20][MAXN],Lnum[20][MAXN];int n,q,high;struct Node{int lef,rig,mid;}T[MAXN<<2];void Build(int u,int l,int r,int d){T[u].lef=l;T[u].rig=r;T[u].mid=(l+r)>>1;if(l==r)return;int mid=T[u].mid;int lsame=mid-l+1;for(int i=l;i<=r;i++){if(val[d][i]<sorted[mid])lsame--;}int p=T[u].lef,q=T[u].mid+1,same=0;for(int i=l;i<=r;i++){if(i==l)Lnum[d][i]=0;else Lnum[d][i]=Lnum[d][i-1];if(val[d][i]<sorted[mid]){val[d+1][p++]=val[d][i];Lnum[d][i]++;}else if(val[d][i]>sorted[mid]){val[d+1][q++]=val[d][i];}else {if(same<lsame){val[d+1][p++]=val[d][i];Lnum[d][i]++;same++;}else val[d+1][q++]=val[d][i];}}Build(lson,l,mid,d+1);Build(rson,mid+1,r,d+1);}int Query(int u,int l,int r,int d,int k){if(l==r)return val[d][l];else {int n1,n2;if(l==T[u].lef){n1=0;n2=Lnum[d][r];}else {n1=Lnum[d][l-1];n2=Lnum[d][r]-n1;}if(n2>=k){int newl=T[u].lef+n1;int newr=T[u].lef+n1+n2-1;return Query(lson,newl,newr,d+1,k);}else {int newl=T[u].mid+1+(l-T[u].lef-n1);int newr=newl+(r-l+1-n2)-1;return Query(rson,newl,newr,d+1,k-n2);}}}int bsearch(int l,int r,int key){int mid;int low=1,high=r-l+1;while(low<high){mid=low+(high-low)/2;int tmp=Query(1,l,r,0,mid);if(tmp<=key)low=mid+1;else high=mid;}if(Query(1,l,r,0,low)>key)return low-1;else return low;}int main(){int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&val[0][i]);sorted[i]=val[0][i];}sort(sorted+1,sorted+1+n);Build(1,1,n,0);int l,r,h;printf("Case %d:\n",cas);while(q--){scanf("%d%d%d",&l,&r,&h);printf("%d\n",bsearch(l+1,r+1,h));//Query(1,l+1,r+1,0,2);}}}