思路：裸的划分树
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define Maxn 100010 #define inf 0x7fffffff #define lson(x) (x<<1) #define rson(x) ((x<<1)|1) #define mid ((tree[po].l+tree[po].r)>>1) using namespace std; struct Tree{ int l,r; }tree[Maxn*4]; int sorted[Maxn]; int val[20][Maxn],toLeft[20][Maxn]; void BuildTree(int l,int r,int dep,int po) { tree[po].l=l,tree[po].r=r; if(l==r) return ; int same=mid-l+1,i; for(i=l;i<=r;i++) if(val[dep][i]<sorted[mid]) same--; int lpos=l,rpos=mid+1; for(i=l;i<=r;i++) { if(i==l) toLeft[dep][i]=0; else toLeft[dep][i]=toLeft[dep][i-1]; if(val[dep][i]<sorted[mid]) toLeft[dep][i]++,val[dep+1][lpos++]=val[dep][i]; else if(val[dep][i]>sorted[mid]) val[dep+1][rpos++]=val[dep][i]; else if(same) toLeft[dep][i]++,val[dep+1][lpos++]=val[dep][i],same--; else val[dep+1][rpos++]=val[dep][i]; } BuildTree(l,mid,dep+1,lson(po)); BuildTree(mid+1,r,dep+1,rson(po)); } int query(int l,int r,int k,int dep,int po) { if(l==r) return val[dep][l]; int vd,invd; if(l==tree[po].l) vd=toLeft[dep][r],invd=0; else vd=toLeft[dep][r]-toLeft[dep][l-1],invd=toLeft[dep][l-1]; if(vd>=k){ int newl=tree[po].l+invd; int newr=tree[po].l+vd+invd-1; return query(newl,newr,k,dep+1,lson(po)); } else{ int ss=l-tree[po].l-invd; int s=r-l+1-vd; int newl=mid+ss+1; int newr=mid+ss+s; return query(newl,newr,k-vd,dep+1,rson(po)); } } int main() { int n,m,i,j,k,s,t,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&val[0][i]); sorted[i]=val[0][i]; } sort(sorted+1,sorted+1+n); BuildTree(1,n,0,1); for(i=1;i<=m;i++) { scanf("%d%d%d",&s,&t,&k); printf("%d ",query(s,t,k,0,1)); } } return 0; }