题目链接：传送门
题目大意：长为 n 的数组，m 次询问，每次问区间 [l,r] 内第 k 小的数。
题目思路：主席树
应该是按权值建立线段树，先将权值离散化，然后利用前缀和的思想来解决。
主席树还是有点难理解，，，
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 100005 #define maxn 30010 typedef pair<int,int> PII; typedef long long LL; LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int n,m,k,sz,L,R; int a[N],b[N],c[N]; int root[N]; struct Seg{ int l,r,v; }seg[N*30]; void update(int &rot,int rt,int l,int r){ seg[++sz]=seg[rot],rot=sz; ++seg[rot].v; if(l==r)return; int mid=l+r>>1; if(L<=mid)update(seg[rot].l,lson); else update(seg[rot].r,rson); } int query(int rt,int l,int r,int k){ if(l==r)return a[l]; int num=seg[seg[R].l].v-seg[seg[L].l].v; int mid=l+r>>1; if(num>=k){ L=seg[L].l;R=seg[R].l; return query(lson,k); } else{ L=seg[L].r;R=seg[R].r; return query(rson,k-num); } } int main(){ int i,j,group,x,y; n=read();m=read(); for(i=1;i<=n;++i)a[i]=read(),c[i]=b[i]=a[i]; sort(a+1,a+n+1); int _n=unique(a+1,a+n+1)-a; for(i=1;i<=n;++i)b[i]=lower_bound(a+1,a+_n+1,b[i])-a; for(i=1;i<=n;++i)L=b[i],update(root[i]=root[i-1],1,1,n); while(m--){ x=read(),y=read(),k=read(); L=root[x-1];R=root[y]; printf("%d ",query(1,1,n,k)); } return 0; }