分析：以前是划分树，感觉难写又不好记（当然肯定是因为我弱），然后学习了主席树（主席树好写），
我感觉CLJ神犇的论文就写的很好，其实就是若干棵权值线段树的建立，以及共用节点，同样的权值线段树是可以相加相减的
反正高度仰慕
#include#include #include #include using namespace std;const int N = 1e5+5;const int INF=0x3f3f3f3f;typedef unsigned long long ULL;typedef long long LL;int a[N],n,q;struct ZXTree{ struct Node{ int l,r,v; }o[N*25]; int sz,root[N],pos[N],c[N]; void update(int &rt,int l,int r,int x){ o[++sz]=o[rt],rt=sz; ++o[rt].v; if(l==r)return; int m=(l+r)>>1; if(x<=m)update(o[rt].l,l,m,x); else update(o[rt].r,m+1,r,x); } int query(int x,int y,int k){ int l=1,r=n; x=root[x-1],y=root[y]; while(l!=r){ int m=(l+r)>>1,t=o[o[y].l].v-o[o[x].l].v; if(k<=t) x=o[x].l,y=o[y].l,r=m; else x=o[x].r,y=o[y].r,l=m+1,k-=t; } return a[l]; } void init(){ root[0]=sz=0; for(int i=1;i<=n;++i) scanf("%d",&a[i]),c[i]=a[i]; sort(a+1,a+1+n); int cnt=1; for(int i=2;i<=n;++i) if(a[i]!=a[i-1])a[++cnt]=a[i]; for(int i=1;i<=n;++i) pos[i]=lower_bound(a+1,a+1+cnt,c[i])-a; for(int i=1;i<=n;++i) update(root[i]=root[i-1],1,n,pos[i]); }}solve; int main(){ scanf("%d%d",&n,&q); solve.init(); while(q--){ int x,y,k; scanf("%d%d%d",&x,&y,&k); printf("%d\n",solve.query(x,y,k)); } return 0;}