题目链接：https://www.luogu.com.cn/problem/P3834
对于区间查询第k小的问题，在区间数量达到5e5的时候是难以用朴素数据结构实现的，这时候主席树就应运而生了，主席树的最基础模板就是查询区间第k小树，其实他在可持久化操作上是十分上手的。主席树在线段树和离散化的基础上实现，树中每一个结点存的是当前结点代表的区间中数的数量，所以初始时刻每个结点的值都是零。然后要插入一个数a到达位置a，并且向上更新所有包含位置a的区间。主席树中每次要插入一个数就新建O(logn）量级的结点，其余结点与前一个树共用，这就实现了空间复杂度的最小化和空间的充分利用。我们在查询[L,R]区间的第K大的数的时候就要利用主席树的函数性质，即其各结点状态可减性，我们只要使得根节点编号为R的与根节点编号为L-1的两个树在结点同步时相减就能得到一棵[L,R]区间状态的树，进而用分治的思想查询树中的第K小。
以下是我手写的一份模板，用的是struct存状态，主席树的代码还是非常简单的，笔者为了让读者更好地理解，写了详细的注释：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define mp(a,b) make_pair((a),(b))
#define P pair<int,int>
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
const int maxn=2e5+;
int n,m;
int a[maxn];
vector<int>v;//离散化之后将内容存储在vector中
int getid(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+;//下标是从1开始直到n结束
}
struct node{
int l,r,sum;
//分别保存左右子树的根节点的编号以及当前结点的数值，
//在还没插入点信息的时候子树中每个结点的值都是0，所以主席树不需要建树，是边插入边建树的
}t[maxn*]; //适应O(nlogn)空间需求，2^40次方大小的数据是不可能的，所以可以根据习惯进行选择
int cnt=,root[maxn];
//权值线段树中插入的值p就是插到位置p ,由于当前结点是需要变化的，所以传入引用使他指向内存池中新的结点
void insert(int l, int r,int pre,int& now,int p)//参数中有前面一棵树的结点以及当前树的结点，
{
t[++cnt]=t[pre];//从内存池中生成一个根结点并将前面树的根节点复制到其中，
now=cnt; //使当前结点指向新生成的根结点，
t[now].sum++;
//要在第p位上插入，所以当前访问的结点是一定是增1的，
//后面我们将会决定访问左子树的结点还是右子树的结点
if(l==r)return;//到达了点信息而且前面已经在叶子结点上面更新过点信息，所以直接return
int m=l+r>>;
//如果左子树的区间包括了p点就向左子树递归，否则走右子树，同时也要分别移动到左子树和右子树
if(p<=m)insert(l,m,t[pre].l,t[now].l,p);
else insert(m+,r,t[pre].r,t[now].r,p);
}
int query(int l,int r,int L,int R,int k)//两个结点同步相减
{
if(l==r)return l;//返回的是点信息，就是离散化之后的坐标，便于之后通过vector进行索引
int m=l+r>>;
int tmp=t[t[R].l].sum-t[t[L].l].sum;//先获取两棵树左子树的键值之差决定向哪一棵数递归
if(k<=tmp)return query(l,m,t[L].l,t[R].l,k);
else return query(m+,r,t[L].r,t[R].r,k-tmp);//如果tmp<k,就查询右子树中的第k-tmp小的数，有点分治的意味
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
scan(n);
scan(m);
f(i,,n)
{
scan(a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
//将数列先排序再去重放入vector中以便通过位置获取在线段树中代表的区间点信息
v.erase(unique(v.begin(),v.end()),v.end());
//unique函数将不重复元素放到vector的前部，
//返回的时所有不重复元素的下一个位置，所以将后面的元素删去就可以离散的成为线段树的坐标点信息
f(i,,n)
{
insert(,n,root[i-],root[i],getid(a[i]));//在第i-1棵树上建第i棵树，所以传入的是两棵树的根节点
}
int l,r,k;
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
pf("%d\n",v[query(,n,root[l-],root[r],k)-]);
//查询[l,r]区间更新的信息，实现动态查询第k小，
//注意vector中下标是从0开始的，而线段树中下标是从1开始的，所以错位了1，为了达到原来的元素就要减一
}
}
hdu2665 Kth number:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define mp(a,b) make_pair((a),(b))
#define P pair<int,int>
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
const int maxn=2e5+;
int n,m,q;
vector<int> v;
int cnt,root[maxn];
int getid(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+;
}
int a[maxn];
struct node{
int l,r,sum;
}t[maxn*];
void insert(int l,int r,int pre,int &now,int pos)
{
t[++cnt]=t[pre];
now=cnt;
t[now].sum++;
if(l==r)return;
int m=l+r>>;
if(pos<=m)insert(l,m,t[pre].l,t[now].l,pos);
else insert(m+,r,t[pre].r,t[now].r,pos);
}
int query(int l,int r,int L,int R,int k)
{
if(l==r)return l;
int tmp=t[t[R].l].sum-t[t[L].l].sum;
int m=l+r>>;
if(k<=tmp)return query(l,m,t[L].l,t[R].l,k);
else return query(m+,r,t[L].r,t[R].r,k-tmp);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
scan(q);
f(kk,,q)
{
scan(n);scan(m);
v.clear();
cnt=;
mem(root,);
f(i,,n)
{
scan(a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
f(i,,n)insert(,n,root[i-],root[i],getid(a[i]));
int l,r,k;
f(tt,,m)
{
scanf("%d%d%d",&l,&r,&k);
pf("%d",v[query(,n,root[l-],root[r],k)-]);
pf("\n");
}
}
}