写这坨答辩的时候我脑袋糊成了一团平衡树 —— 上下翻转。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s = 0,f = 1;char c = getchar();
	while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
	while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
	return s*f;
}
const int N = 2e6 + 5;
int n,m;
int root[N],a[N];
struct President_Tree{
	int idx;
	struct node{
		int l,r,val;
	}tree[N<<4];
	int build(int l,int r){
		idx++;
		if (l == r){
			tree[idx].val = a[l];
			return idx;
		}
		int mid = (l + r)/2;
		tree[idx].l = build(l,mid);
		tree[idx].r = build(mid+1,r);
		return idx;
	}
	int update(int node,int l,int r,int x,int val){
	    tree[++idx] = tree[node];
		if (l == r){
			tree[node].val = val;
			return idx;
		}
		int mid = (l + r)/2;
		if (x <= mid) tree[idx].l = update(tree[idx].l,l,mid,x,val);
		else tree[idx].r = update(tree[idx].r,mid+1,r,x,val);
		return idx;
	}
	int query(int node,int l,int r,int x){
		if (l == r)
		    return tree[node].val;
		int mid = (l + r)/2;
		if (x <= mid)
		    return query(tree[node].l,l,mid,x);
		return query(tree[node].r,mid+1,r,x);
	}
}Tree;
int main()
{
    n = read(); m = read();
    for (int i=1;i<=n;i++)
        a[i] = read();
    root[0] = Tree.build(1,n);
    for (int i=1;i<=m;i++){
    	int rt,op,x,y;
    	rt = read();op = read();x = read();
    	if (op == 1){
    		y = read();
    		root[i] = Tree.update(root[rt],1,n,x,y);
		} else {
			printf("%d\n",Tree.query(root[rt],1,n,x));
			root[i] = root[rt];
		}
	}
	return 0;
}