P3919 【模板】可持久化线段树 1（可持久化数组）

传送门

主席树$PST$PST板子题，主要思路就是通过只增加更新结点上路径的结点，其他结点沿用原来的结点，每次更新和询问时间复杂度$:O(logn)$:O(logn)。

相应的空间也会增加$nlogn$nlogn个，所以空间要开大为$O(n+nlogn)$O(n+nlogn)

时间复杂度：$O(mlogn)$O(mlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5,M=N*21,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
template<class T>
inline void read(T &x){ 
	x=0;int w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	x*=w; 
}
int a[N],rt[M];
struct PST{
	int lx[M],rx[M],val[M],cnt;
	inline void build(int &x,int l,int r){	//建树 
		x=++cnt;
		if(l==r){read(val[x]);return;}	//边输入边建树. 
		int mid=(l+r)>>1;
		build(lx[x],l,mid),build(rx[x],mid+1,r);
	}
	inline void upd(int &x,int pre,int l,int r,int i,int v){
		x=++cnt,lx[x]=lx[pre],rx[x]=rx[pre],val[x]=val[pre];//更新路径上的结点. 
		if(l==r){val[x]=v;return;}
		int mid=(l+r)>>1;
		if(i<=mid) upd(lx[x],lx[pre],l,mid,i,v);
		else upd(rx[x],rx[pre],mid+1,r,i,v);
	}
	inline int query(int x,int l,int r,int i){	//查询. 
		if(l==r) return val[x];
		int mid=(l+r)>>1;
		if(i<=mid) return query(lx[x],l,mid,i);
		else return query(rx[x],mid+1,r,i);
	}
}T;
int main(){
	int n,m;
	read(n),read(m);
	T.build(rt[0],1,n);
	for(reg int i=1;i<=m;i++){
		int pre,op,id,v;
		read(pre),read(op),read(id);
		if(op==1) read(v),T.upd(rt[i],rt[pre],1,n,id,v);
		if(op==2) printf("%d\n",T.query(rt[pre],1,n,id)),rt[i]=rt[pre];
	}
	return 0;
}