思路：裸的划分树
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #define Maxn 100010 #define lson(x) x<<1 #define rson(x) x<<1|1 #define mid ((tree[po].l+tree[po].r)>>1) using namespace std; int val[20][Maxn],toLeft[20][Maxn],sorted[Maxn]; struct Tree{ int l,r; }tree[Maxn*4]; 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=invd+tree[po].l; int newr=invd+vd+tree[po].l-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,l,r,Case=0,t,x; while(scanf("%d",&n)!=EOF) { 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); printf("Case %d: ",++Case); scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d",&l,&r); printf("%d ",query(l,r,(r-l+2)/2,0,1)); } } return 0; }