这是个非常经典的主席树入门题——静态区间第K小
数据已经过加强，请使用主席树。同时请注意常数优化
如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。
输入格式：
第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。
第二行包含N个正整数，表示这个序列各项的数字。
接下来M行每行包含三个整数 $l,r,k$ , 表示查询区间 $[l,r]$ 内的第k小值。
输出格式：
输出包含k行，每行1个正整数，依次表示每一次查询的结果
数据范围：
对于20%的数据满足： $1 \leq N, M \leq 10$
对于50%的数据满足： $1 \leq N, M \leq 10^3$
对于80%的数据满足： $1 \leq N, M \leq 10^5$
对于100%的数据满足： $1 \leq N, M \leq 2\cdot 10^5$
对于数列中的所有数 $a_i$? ，均满足 $-{10}^9 \leq a_i \leq {10}^9$
样例数据说明：
N=5，数列长度为5，数列从第一项开始依次为 $[25957,6405,15770,26287,26465]$
第一次查询为 $[2,2]$ 区间内的第一小值，即为6405
第二次查询为 $[3,4]$ 区间内的第一小值，即为15770
第三次查询为 $[4,5]$ 区间内的第一小值，即为26287
第四次查询为 $[1,2]$ 区间内的第二小值，即为25957
第五次查询为 $[4,4]$ 区间内的第一小值，即为26287
分析：
主席树入门题。
一直说要学习主席树来的，但是直到今天才实现。具体思想蒟蒻也就不赘述，贴一波布雷芙$\cdot$卡托尔学姐（误）的博客。
Code：
//It is made by HolseLee on 29th July 2018 //Luogu.org P3834 #include<bits/stdc++.h> using namespace std; const int N=2e5+7; int n,m,tot,cnt,a[N],b[N],rk[N],rt[N]; struct President_tree{ int ls,rs,sum; }t[N*20]; int read() { char ch=getchar();int num=0;bool flag=false; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){num=(num<<3)+(num<<1)+ch-‘0‘;ch=getchar();} return flag?-num:num; } inline void build(int l,int r,int &node) { node=++cnt; if(l==r)return ; int mid=(l+r)>>1; build(l,mid,t[node].ls); build(mid+1,r,t[node].rs); } inline void update(int l,int r,int &node,int last,int tar) { node=++cnt;t[node]=t[last];++t[node].sum; if(l==r)return; int mid=(l+r)>>1; if(tar<=mid)update(l,mid,t[node].ls,t[last].ls,tar); else update(mid+1,r,t[node].rs,t[last].rs,tar); } inline int quary(int l,int r,int node,int last,int tar) { if(l==r)return a[l]; int now=t[t[node].ls].sum-t[t[last].ls].sum,mid=(l+r)>>1; if(tar<=now)return quary(l,mid,t[node].ls,t[last].ls,tar); else return quary(mid+1,r,t[node].rs,t[last].rs,tar-now); } int main() { n=read();m=read(); for(int i=1;i<=n;++i){ a[i]=read();b[i]=a[i]; } sort(a+1,a+n+1); tot=unique(a+1,a+n+1)-a-1; build(1,tot,rt[0]); for(int i=1;i<=n;++i) rk[i]=lower_bound(a+1,a+tot+1,b[i])-a; for(int i=1;i<=n;i++) update(1,tot,rt[i],rt[i-1],rk[i]); int l,r,k; for(int i=1;i<=m;++i){ l=read();r=read();k=read(); printf("%d\n",quary(1,tot,rt[r],rt[l-1],k)); } return 0; }
洛谷P3834 [模板]可持久化线段树1（主席树） [主席树]
原文：https://www.cnblogs.com/cytus/p/9385383.html