题意：给定一个数组，每次查询第l到r区间的第k大值
解法嘛，当然是主席树，主席树即可持久化线段树，什么叫可持久化呢，就是指能够访问历史版本的数据结构，那么对于某些只能离线处理的题目强制在线之后 ，可以通过在线处理操作
经过这题总算对可持久化线段树有了些了解，我们开始先建一颗空树，然后对于每次修改我们只会修改logn个点，我们可以新建logn个来避免每次都新建一颗线段树导致的爆空间，
对于这题来说我们线段树中维护的是这个区间的点的个数，插入的时候按权值大小插入，对于l到r我们可以通过1-r减去1-(l-1)来求出l到r的，对于第k大我们可以用求平衡树第k大的做法，每次查询节点个数看往左走还是往右走
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 //#define ls l,m,rt<<1 //#define rs m+1,r,rt<<1|1 #define pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f; int a[N],b[N],tot,rt[N*20],ls[N*20],rs[N*20],sum[N*20]; void build(int &o,int l,int r) { o=++tot; sum[o]=0; if(l==r)return; int m=(l+r)>>1; build(ls[o],l,m); build(rs[o],m+1,r); } void update(int &o,int l,int r,int last,int p) { o=++tot; ls[o]=ls[last]; rs[o]=rs[last]; sum[o]=sum[last]+1; if(l==r)return ; int m=(l+r)>>1; if(p<=m)update(ls[o],l,m,ls[last],p); else update(rs[o],m+1,r,rs[last],p); } int query(int ss,int tt,int l,int r,int x) { if(l==r)return l; int m=(l+r)>>1; int cnt=sum[ls[tt]]-sum[ls[ss]]; if(x<=cnt)query(ls[ss],ls[tt],l,m,x); else query(rs[ss],rs[tt],m+1,r,x-cnt); } void work(int sz) { int ql,qr,x; scanf("%d%d%d",&ql,&qr,&x); int ans=query(rt[ql-1],rt[qr],1,sz,x); printf("%d ",b[ans]); } void debug() { puts("***********"); for(int i=1;i<=tot;i++) printf("%d %d %d ",ls[i],rs[i],sum[i]); puts("***********"); } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; scanf("%d",&t); while(t--) { int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int sz=unique(b+1,b+1+n)-(b+1); tot=0; build(rt[0],1,sz); // debug(); for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+sz,a[i])-b; for(int i=1;i<=n;i++)update(rt[i],1,sz,rt[i-1],a[i]); // debug(); while(q--)work(sz); } return 0; } /******************** 1 4 2 4 1 3 2 2 3 2 ********************/