例题：poj2104
讲解，推荐博客：
数组版：
#include#include using namespace std;const int N=100001;int l_child[N*18],r_child[N*18],sum[N*18];int n,m,a[N],hash[N],cnt,root[N];int x,y,k;void discrete(){ sort(hash+1,hash+n+1); cnt=unique(hash+1,hash+n+1)-(hash+1); for(int i=1;i<=n;i++) a[i]=lower_bound(hash+1,hash+cnt+1,a[i])-hash;}int init(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int query(int x,int y,int l,int r,int k){ if(l==r) return l; int mid=l+r>>1,tmp=sum[l_child[y]]-sum[l_child[x]]; if(tmp>=k) return query(l_child[x],l_child[y],l,mid,k); else return query(r_child[x],r_child[y],mid+1,r,k-tmp);}int tot=0;void build(int x,int &y,int l,int r,int v){ sum[y=++tot]=sum[x]+1; if(l==r) return; int mid=l+r>>1; if(v<=mid) { r_child[y]=r_child[x]; build(l_child[x],l_child[y],l,mid,v); } else { l_child[y]=l_child[x]; build(r_child[x],r_child[y],mid+1,r,v); }}int main(){ n=init();m=init(); for(int i=1;i<=n;i++) a[i]=init(),hash[i]=a[i]; discrete(); //for(int i=1;i<=n;i++) printf("%d ",a[i]); for(int i=1;i<=n;i++) build(root[i-1],root[i],1,cnt,a[i]); for(int i=1;i<=m;i++) { x=init();y=init();k=init(); printf("%d\n",hash[query(root[x-1],root[y],1,cnt,k)]); }}
指针版：TLE
#include#include #define N 100001using namespace std;int n,m,a[N],hash[N];int tot,cnt;struct node{ node * l,* r; int sum;};node * root[N]; void discrete(){ sort(a+1,a+n+1); tot=unique(a+1,a+n+1)-(a+1); for(int i=1;i<=n;i++) hash[i]=lower_bound(a+1,a+n+1,hash[i])-a;}inline node * build(node * pre,int l,int r,int w){ node *neww=new node(); //node * neww=(node *)malloc(sizeof(node)); neww->sum=pre->sum+1; if(l==r) return neww; int mid=l+r>>1; if(w<=mid) { neww->r=pre->r; neww->l=build(pre->l,l,mid,w); } else { neww->l=pre->l; neww->r=build(pre->r,mid+1,r,w); } return neww;}inline int query(node * x,node * y,int k,int l,int r){ if(l==r) return l; int mid=l+r>>1,tmp=y->l->sum-x->l->sum; if(k<=tmp) return query(x->l,y->l,k,l,mid); else return query(x->r,y->r,k-tmp,mid+1,r);}node * null(int ll,int rr){ node *neww=new node(); //node * neww=(node *)malloc(sizeof(node)); neww->l=neww->r=NULL; neww->sum=0; if(ll==rr) return neww; int mid=ll+rr>>1; neww->l=null(ll,mid); neww->r=null(mid+1,rr); return neww;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) {scanf("%d",&a[i]);hash[i]=a[i];} discrete(); root[0]=null(1,n); for(int i=1;i<=n;i++) root[i]=build(root[i-1],1,n,hash[i]); int x,y,k; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&k); printf("%d\n",a[query(root[x-1],root[y],k,1,n)]); }}