【模板】可持久化线段树

       可持久化线段树用于保存线段树的所有历史版本，通过共用数据减少时间和空间复杂度。

线段树的动态开点

       回想树状数组求逆序对，方法以权值为下标从前往后更新树状数组，当值域范围过大时，采取的方式是离散化。如果用线段树可否完成呢？

       和树状数组相同的方式，建立权值线段树即可，众所周知线段树要开4倍空间，值域过大时空间上难以接受。

       比较简单的解决方案就是先离线出来然后离散化。事实上，线段树中节点存在着大量的浪费，因此需要一种随用随开点的动态开点的方式，类似于Trie树的insert操作，当当前节点为空时直接创建新节点，不同于传统堆式存储，动态开点线段树的编号是按照创建顺序从小到大赋值的。因此需要保存其左右子节点的编号。

       每次开点只需增加 l o g N logN logN个节点，因此其空间复杂度为 O ( M   l o g N ) O(M\ logN) O(M logN)， M M M为询问数， N N N为值域。

inline void push_up(int rt){
	tr[rt].cnt=tr[tr[rt].lson].cnt+tr[tr[rt].rson].cnt;
} 
void update(int &rt,int l,int r,int k){
	if(!rt)	rt=++ver; 
	if(l==r){++tr[rt].cnt;return;}
	int mid=l+r>>1;
	if(k<=mid)	update(tr[rt].lson,l,mid,k);
	else		update(tr[rt].rson,mid+1,r,k);
	push_up(rt);
}
int query(int rt,int l,int r,int x,int y){
	if(!rt)	return 0;
	if(l>=x && r<=y)	return tr[rt].cnt;
	int res=0,mid=l+r>>1;
	if(x<=mid)	res+=query(tr[rt].lson,l,mid,x,y);
	if(y>mid)	res+=query(tr[rt].rson,mid+1,r,x,y);
	return res;
}

可持久化线段树

       回想用线段树查询区间 k t h kth kth元素的方法，即建立权值线段树，查询时线段树上二分。

       如果查询 [ L , R ] [L,R] [L,R]内的 k t h kth kth元素呢，暴力的做法就是每次在 [ 1 , i ] [1,i] [1,i]区间上建立一棵线段树，用 [ 1 , R ] [1,R] [1,R]和 [ 1 , L − 1 ] [1,L-1] [1,L−1]两个版本的线段树即可求解。时间复杂度 O ( M N   l o g N ) O(MN\ logN) O(MN logN)。

       考虑从 [ 1 , R ] [1,R] [1,R]到 [ 1 , R + 1 ] [1,R+1] [1,R+1]时，需要更新的节点只有 l o g N logN logN个,有无办法使得不同版本的线段树共用信息呢？动态开点！

       动态开点时我们保存了所有节点及其子节点的编号，每次在建立一个新版本的线段树时，对于不需要增加的节点，直接与上一版本的节点共用编号；对于需要增加的节点，它们在一条链上，因此直接update时增加节点即可。只需保存每个版本线段树的根节点编号就能获得全部信息，初始版本的线段树建成空树即可。时间复杂度 O ( ( N + M ) l o g N ) O((N+M)logN) O((N+M)logN)， N N N过大时需要离散化。

       模板题LuoguP3834 传送门Biu~

#include<bits/stdc++.h>
#define N 200005
#define NN 4000005
#define LL long long
#define INF 1e9
using namespace std;
inline int Fread(){
    int val=0;bool sign=false;char ch=0;
    while(ch<'0' || ch>'9') sign|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') val=(val<<3)+(val<<1)+(ch^48),ch=getchar();
    return sign?(~val+1):val;
}
int a[N],a_[N],q[N],ver=1;
struct Node{
	int val,lson,rson;
}tr[NN];
void build(int &rt,int l,int r){
	rt=++ver;
	if(l==r)	return;
	int mid=l+r>>1;
	build(tr[rt].lson,l,mid),build(tr[rt].rson,mid+1,r);
}
void update(int &rt,int pre,int l,int r,int x){
	rt=++ver,tr[rt].lson=tr[pre].lson,tr[rt].rson=tr[pre].rson,tr[rt].val=tr[pre].val+1;
	if(l==r)	return;
	int mid=l+r>>1;
	if(x<=mid)	update(tr[rt].lson,tr[pre].lson,l,mid,x);
	else	update(tr[rt].rson,tr[pre].rson,mid+1,r,x);
}
int query(int x,int y,int l,int r,int k){
	if(l==r)	return l;
	int cur=tr[tr[y].lson].val-tr[tr[x].lson].val;
	int mid=l+r>>1;
	if(cur>=k)	return query(tr[x].lson,tr[y].lson,l,mid,k);
	else	return query(tr[x].rson,tr[y].rson,mid+1,r,k-cur);
}
signed main(){
	int n=Fread(),m=Fread();
	for(int i=1;i<=n;++i)	a[i]=Fread(),a_[i]=a[i];
	sort(a_,a_+n+1);
	int cnt=unique(a_+1,a_+n+1)-a_-1;
	build(q[0],1,cnt);
	for(int i=1;i<=n;++i)	update(q[i],q[i-1],1,cnt,lower_bound(a_+1,a_+cnt+1,a[i])-a_);
	while(m--){
		int x=Fread(),y=Fread(),k=Fread();
		printf("%d\n",a_[query(q[x-1],q[y],1,cnt,k)]);
	}
	return 0;
}