RT,wtcl

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') flag=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return flag?~x+1:x;
}
inline void write(int x){
	if(x<0){putchar('-');x=(~x+1);}
	if(x/10) write(x/10);
	putchar((x%10)^48);
	return;
}
const int N=1e6+5;
struct SegmentTree{
	int data;
	int lch,rch;
}tree[N<<5];
int tot,a[N],n;
inline int new_node(int p){
	tree[++tot]=tree[p];
	return tot;
}
inline int build(int p,int l,int r){
	p=++tot;
	if(l==r){
		tree[p].data=a[l];
		return p;
	}
	int mid=(l+r)>>1;
	tree[p].lch=build(tree[p].lch,l,mid);
	tree[p].rch=build(tree[p].rch,mid+1,r);
	return p;
}
inline int change(int p,int l,int r,int pos,int value){
	p=new_node(p);
	if(l==r){
		tree[p].data=value;
		return p;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) change(tree[p].lch,l,mid,pos,value);
	if(pos>mid) change(tree[p].rch,mid+1,r,pos,value);
	return p;
}
inline int ask(int p,int l,int r,int pos){
	if(l==r) return tree[p].data;
	int mid=(l+r)>>1;
	if(pos<=mid) return ask(tree[p].lch,l,mid,pos);
	if(pos>mid) return ask(tree[p].rch,mid+1,r,pos);
}
vector<int> root;
signed main(){
	n=read();int kkk=read();
	for(int i=1;i<=n;++i) a[i]=read();
	root.push_back(build(0,1,n));
	while(kkk--){
		int now=read(),opt=read();
		if(opt==1) root.push_back(change(root[now],1,n,read(),read()));
		else{
			write(ask(root[now],1,n,read())),puts("");
			root.push_back(root[now]);
		}
	}
	return 0;
}

样例也有一点问题，调了很久了。。。