RT
只有sub2的第一个点过了
#include<bits/stdc++.h>
using namespace std;
const int MX=21*1000000+10;
#define LL long long
#define inf 0x7fffffff
struct tk
{
int l,r;
int value;
}tree[MX];
int top=0;
int root[MX];
int n,m;
int w[MX];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int create(int node)
{
tree[++top]=tree[node];
return top;
}
inline int build(int now,int l,int r)
{
top++;
now=top;
if(l==r)
{
tree[now].value=w[l];
return top;
}
int mid=(l+r)>>1;
tree[now].l=build(tree[now].l,l,mid);
tree[now].r=build(tree[now].r,mid+1,r);
return now;
}
inline int updata(int now,int l,int r,int x,int nval)
{
now=create(now);
if(l==r)
{
tree[now].value=nval;
}
else
{
int mid=(l+r)>>1;
if(x<=mid)
{
tree[now].l=updata(tree[now].l,l,mid,x,nval);
}
else
{
tree[now].l=updata(tree[now].r,mid+1,r,x,nval);
}
}
return now;
}
inline int query(int now,int l,int r,int x)
{
if(l==r)
{
return tree[now].value;
}
else
{
int mid=(l+r)>>1;
if(x<=mid) return query(tree[now].l,l,mid,x);
else return query(tree[now].r,mid+1,r,x);
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)
{
w[i]=read();
}
root[0]=build(0,1,n);
for(int i=1;i<=m;i++)
{
int v1,cz,loc;
v1=read(),cz=read(),loc=read();
if(cz==1)
{
int nval;
nval=read();
root[i]=updata(root[v1],1,n,loc,nval);
}
else if(cz==2)
{
printf("%d\n", query(root[v1],1,n,loc));
root[i]=root[v1];
}
}
return 0;
}