这是个非常经典的主席树入门题——静态区间第K小。
基本思想是像维护前缀和一样，维护每个区间\([1...i]\)中的数，在\([1...j]\)范围的数的个数。因为大多数状态是重复的所以我们并不需要开\(n\)个线段树，只需要连接到一些没有改变的子状态上就可以了。
对于查询区间\([ql...qr]\)内第\(k\)小的，我们可以判断，对于当前结点，如果\(l[qr]-l[ql]>=k\)，那么\(k\)小值在其左儿子，否则在右儿子。
数据很大需要进行离散化。
#include#include #include #include #include #define MAXN 200233using namespace std;int tot=0,n,m,len;struct qwq{ int ans,l,r;}f[MAXN<<5];int id[MAXN]; int a[MAXN],b[MAXN];#define mid ((l+r)>>1)void build(int &cur,int l,int r){ cur=++tot; if (l==r) return; build(f[cur].l,l,mid); build(f[cur].r,mid+1,r);}int modify(int cur,int l,int r,int del){ int n_cur=++tot;// printf(":::%d",n_cur); f[n_cur].l=f[cur].l; f[n_cur].r=f[cur].r; f[n_cur].ans=f[cur].ans+1; if (l==r) return n_cur; if (del<=mid) f[n_cur].l=modify(f[n_cur].l,l,mid,del); else f[n_cur].r=modify(f[n_cur].r,mid+1,r,del); return n_cur;}int query(int ql,int qr,int l,int r,int del){ int x=f[f[qr].l].ans-f[f[ql].l].ans;// printf("QAQAQ&$@*#R&!@BGYUE:::%d",x); if (l==r) return l; if (x>=del) return query(f[ql].l,f[qr].l,l,mid,del); else return query(f[ql].r,f[qr].r,mid+1,r,del-x);}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); len=unique(b+1,b+n+1)-b-1;// for (int i=1;i<=len;i++)// {// printf("%d ",b[i]);// }printf("\n\n\n"); build(id[0],1,len); for (int i=1;i<=n;i++) { id[i]=modify(id[i-1],1,len,lower_bound(b+1,b+len+1,a[i])-b); }// printf("%%%%%%%%%%qwq\n");// printf("::::::::%d\n",tot);// for (int i=1;i<=tot;i++)// {// printf("%d ",f[id[i]].l);// } int l,r,k; while (m--) { scanf("%d%d%d",&l,&r,&k);// printf("qwq:::%d\n",query(id[l-1],id[r],1,len,k)); printf("%d\n",b[query(id[l-1],id[r],1,len,k)]); } return 0;}