【算法】 主席树

解决问题：m次询问，每次给定一段区间，求静态区间kth。

考虑对每个点i建一棵权值线段树，维护1-i区间里的数出现的次数。
例如给定6个数：1 3 2 3 6 1，第4棵树如下：

n棵权值线段树形状一样，考虑对两棵树相减：第i棵树维护1-i区间里的数出现的次数，第j棵树维护1-j区间里的数出现的次数(i>j)，第i棵减第j棵则得到一棵新的权值线段树，维护j+1-i区间里的数出现的次数。
这就是主席树的一个核心思想：前缀和思想。

现在看主席树的另一个核心思想：空间优化。
建立n棵线段树需要的空间太大了，需要进行优化。观察每次添加新节点时树的变化，发现只有从某个叶子节点到根节点路径上的点的权值发生了变化，其余点权值没变。因此我们新建节点，储存变化后的点。
以下为上例添加第1,2,3个点时的情况：

下面看代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=2e5+9;
const int maxx=1e4+9;

int a[maxn],b[maxn];    //a储存输入数据 b为离散化的结果
int n,m,q,p,sz;     //输入数 询问数 去重后序列长度 新加入点的位置 节点个数
int lc[maxn<<5],rc[maxn<<5],sum[maxn<<5],rt[maxn<<5];
//左儿子编号 右儿子编号 节点权值 每棵树根节点编号

void build(int &rt,int l,int r)
{
    rt=++sz,sum[rt]=0;
    if(l==r) return;
    build(lc[rt],l,(l+r)/2);
    build(rc[rt],(l+r)/2+1,r);
}
int update(int o,int l,int r)
{
    int oo=++sz;
    lc[oo]=lc[o],rc[oo]=rc[o],sum[oo]=sum[o]+1;    //继承原节点的信息，权值加一
    if(l==r) return oo;
    int mid=(l+r)/2;
    if(p<=mid) lc[oo]=update(lc[oo],l,mid);    //修改路径上的点，新建点代替父节点对应的左/右节点
    else rc[oo]=update(rc[oo],mid+1,r);
    return oo;
}
int query(int u,int v,int l,int r,int k)    //u,v为当前两棵线段树的节点编号
{
    if(l==r) return l;    //到叶子节点返回
    int mid=(l+r)/2,x=sum[lc[v]]-sum[lc[u]];    //x表示询问区间内有多少数出现在[l,(l+r)/2]
    if(x>=k) return query(lc[u],lc[v],l,mid,k);
    else return query(rc[u],rc[v],mid+1,r,k-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+1+n);
    q=unique(b+1,b+1+n)-(b+1);    //离散化，以排序去重后的下标代替值
    build(rt[0],1,q);        //建立空树
    for(int i=1;i<=n;i++)
    {
        p=lower_bound(b+1,b+1+q,a[i])-b;    //p的值决定了更新a[i]时变动的节点，以及新增节点
        rt[i]=update(rt[i-1],1,q);
    }
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",b[query(rt[l-1],rt[r],1,q,k)]);
    }
}

最后提供主席树模板题：

https://www.luogu.com.cn/problem/P3834