传送门
题意简述：支持在某个历史版本上修改某一个位置上的值，访问某个历史版本上的某一位置的值。
思路：
用主席树直接维护历史版本即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
const int N=1e6+5;
int n,m,rt[N],a[N];
namespace SGT{
#define lc (son[p][0])
#define rc (son[p][1])
#define mid (l+r>>1)
int son[N*20][2],val[N*20],tot=0;
inline void build(int&p,int l,int r){
p=++tot;
if(l==r){val[p]=a[l];return;}
build(lc,l,mid),build(rc,mid+1,r);
}
inline void update(int&p,int o,int l,int r,int k,int v){
p=++tot,lc=son[o][0],rc=son[o][1];
if(l==r){val[p]=v;return;}
k<=mid?update(lc,son[o][0],l,mid,k,v):update(rc,son[o][1],mid+1,r,k,v);
}
inline int query(int p,int l,int r,int k){
if(l==r)return val[p];
return k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k);
}
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)a[i]=read();
SGT::build(rt[0],1,n);
for(ri op,id,x,i=1;i<=m;++i){
id=read(),op=read(),x=read(),rt[i]=rt[id];
switch(op){
case 1:SGT::update(rt[i],rt[id],1,n,x,read());break;
default:cout<<SGT::query(rt[i],1,n,x)<<'\n';
}
}
return 0;
}