可持久化线段树

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define pb push_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define isZero(d)  (abs(d) < 1e-8)
using namespace std;
const int maxn=1e7+5,INF=0x3f3f3f3f;
const int N=1e6+5;
const int mod=1e9+7;

int no,a[N],version[N];

struct SegmentTree
{
	int l,r,v;
}ST[maxn];

int Build(int L,int R)
{
	int rt=++no;
	if(L==R)
	{
		ST[rt].v=a[L];
		return rt;
	}
	int mid=(L+R)>>1;
	ST[rt].l=Build(L,mid);
	ST[rt].r=Build(mid+1,R);
	return rt;
}

int Update(int pre,int L,int R,int p,int v)
{
	int rt=++no;
	if(L==R)
	{
		ST[rt].v=v;
		return rt;
	}
	ST[rt].l=ST[pre].l;
	ST[rt].r=ST[pre].r;
	int mid=(L+R)>>1;
	if(p<=mid)
		ST[rt].l=Update(ST[pre].l,L,mid,p,v);
	if(p>mid)
		ST[rt].r=Update(ST[pre].r,mid+1,R,p,v);
	return rt;
}

int Query(int rt,int L,int R,int p)
{
	if(L==R)
		return ST[rt].v;
	int mid=(L+R)>>1;
	if(p<=mid)
		return Query(ST[rt].l,L,mid,p);
	if(p>mid)
		return Query(ST[rt].r,mid+1,R,p);
}

int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	rep(i,1,n)
		scanf("%d",&a[i]);
	version[0]=1;
	Build(1,n);
	for(int i=1;i<=m;++i)
	{
		int pre,op,p,v;
		scanf("%d %d %d",&pre,&op,&p);
		if(op==1)
		{
			scanf("%d",&v);
			version[i]=Update(version[pre],1,n,p,v);
		}
		else if(op==2)
		{
			version[i]=version[pre];
			printf("%d\n",Query(version[i],1,n,p));
		}		 
	}   
	return 0;
}

P3834 【模板】可持久化线段树 1（主席树）

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define pb push_back
#define isZero(d)  (abs(d) < 1e-8)
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f;
const int mod=1e9+7;

int n,m,k,no;
int a[maxn],b[maxn],version[maxn];

struct SegmentTree
{
	int ls,rs,v;
}ST[maxn<<5];

int Build(int L,int R)
{
	int rt=++no;
	ST[rt].v=0;
	if(L==R)
	{
		ST[rt].ls=0;
		ST[rt].rs=0;
		return rt;
	}		
	int mid=(L+R)>>1;
	ST[rt].ls=Build(L,mid);
	ST[rt].rs=Build(mid+1,R);
	return rt;
}

int Update(int pre,int p,int L,int R)
{
	int rt=++no;
	ST[rt].ls=ST[pre].ls;
	ST[rt].rs=ST[pre].rs;
	ST[rt].v=ST[pre].v+1;
	if(L==R)
	{
		return rt;
	}
		
	int mid=(L+R)>>1;
	if(p<=mid)
		ST[rt].ls=Update(ST[pre].ls,p,L,mid);
	if(p>mid)
		ST[rt].rs=Update(ST[pre].rs,p,mid+1,R);
	return rt;
}

int Query(int pre,int now,int L,int R,int k)
{
	if(L==R)
		return L;
	int mid=(L+R)>>1;
	int x=ST[ST[now].ls].v-ST[ST[pre].ls].v;
	if(k<=x)
		return Query(ST[pre].ls,ST[now].ls,L,mid,k);
	if(k>x)
		return Query(ST[pre].rs,ST[now].rs,mid+1,R,k-x);
}

int main()
{
	scanf("%d %d",&n,&m);
	rep(i,1,n)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int s=unique(b+1,b+1+n)-b-1;
	version[0]=1;
	Build(1,s);
	
	for(int i=1;i<=n;++i)
	{
		int pos=lower_bound(b+1,b+1+s,a[i])-b;
		version[i]=Update(version[i-1],pos,1,s);
	}
	while(m--)
	{
		int l,r,k;
		scanf("%d %d %d",&l,&r,&k);
		int pos=Query(version[l-1],version[r],1,s,k);
		printf("%d\n",b[pos]);
	}
	return 0;
}