只有 #1 通过了

Code

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=1e6+1;
int tot,root[N];

struct node
{
	int ls,rs;
	int val;
}T[N<<5];

int read() {
	int x=0; bool f=true; char ch=0;
	while (!isdigit(ch)) f&=(f!='-'),ch=getchar();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return f?x:~(--x);
}
void build(int &rt,int l,int r) {
	rt=(++tot); if (l==r) T[rt].val=read();
	else build(T[rt].ls,l,mid),build(T[rt].rs,mid+1,r);
}
void update(int &p,int q,int l,int r,int pos)
{
	p=(++tot); if (l==r) return T[p].val=read(),void();
	if (pos<=mid) update(T[p].ls,T[q].ls,l,mid,pos),T[p].rs=T[q].rs;
	else update(T[p].rs,T[q].rs,mid+1,r,pos),T[p].ls=T[q].ls;
}
int query(int rt,int l,int r,int pos)
{
	if (l==r) return T[rt].val;
	if (pos<=mid) return query(T[rt].ls,l,mid,pos);
	else return query(T[rt].rs,mid+1,r,pos);
}
int main()
{
	int n=read(),m=read();
	build(root[0],1,n);
	for (int i=1;i<=m;i++) {
		int now=read(),op=read(),x=read();
		if (op==1) update(root[i],root[now],1,n,x);
		else root[i]=root[now],printf("%d\n",query(root[i],1,n,x));
	}
	return 0;
}