主席树是可持久化线段树。
当我想知道某个历史状态下的数据，则需要将每一个状态都存下来，可是会MLE。
但是我们可以发现每次修改只会修改\(log_{2} n\)次，也就是增加\(log_{2} n\)个节点。
例题：洛谷P3834
思路：首先离散化，建一棵权值主席树，因为\(r\)历史状态下个数-\((l-1)\)历史状态下个数就是\([l,r]\)中总个数，然后就和权值线段树求第k小一样。
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m;
struct nod{
int zhi;
int id;
}a[200010];
int b[200010];
struct node{
int l,r;
int zs,ys;
int sum;
}tree[10000010];
int tot=0;
int tou[200010];
bool cmp(nod x,nod y){
return x.zhi<y.zhi;
}
void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
tree[i].sum=0;
if(l==r){
return ;
}
int mid=(l+r)/2;
tree[i].zs=++tot;
build(tot,l,mid);
tree[i].ys=++tot;
build(tot,mid+1,r);
return ;
}
void buil(int i,int j,int k){
tree[i]=tree[j];
tree[i].sum++;
if(tree[i].l==tree[i].r){
return ;
}
if(tree[tree[i].zs].r>=k){
tree[i].zs=++tot;
buil(tot,tree[j].zs,k);
}
else{
tree[i].ys=++tot;
buil(tot,tree[j].ys,k);
}
}
int search(int i,int j,int k){
if(tree[i].l==tree[i].r){
return tree[i].l;
}
if(tree[tree[i].zs].sum-tree[tree[j].zs].sum>=k){
return search(tree[i].zs,tree[j].zs,k);
}
else{
return search(tree[i].ys,tree[j].ys,k-tree[tree[i].zs].sum+tree[tree[j].zs].sum);
}
}
int main(){
cin>>n>>m;
tot=1;
tou[0]=1;
build(1,1,n);
for(int i=1;i<=n;i++){
cin>>a[i].zhi;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
b[a[i].id]=i;
}
for(int i=1;i<=n;i++){
tou[i]=++tot;
buil(tot,tou[i-1],b[i]);
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<a[search(tou[r],tou[l-1],k)].zhi<<endl;
}
return 0;
}