rt，本题可以离线做，也就是最最基础的dfs

#include <bits/stdc++.h>
#define MAXNM 1000000
using namespace std;

struct opt {
	int type, loc, val, ans;
	list<int> son;
};

int n, m, k = 0;
int a[MAXNM + 1], ans[MAXNM + 1];
opt op[MAXNM + 1];

void dfs(int k) {
	int cp;
	if(op[k].type == 1) {
		cp = a[op[k].loc];
		a[op[k].loc] = op[k].val;
	}
	if(op[k].type == 2) {
		ans[op[k].ans] = a[op[k].loc];
	}
	for(auto it = op[k].son.begin(); it != op[k].son.end(); it++) {
			dfs(*it);
	}
	if(op[k].type == 1) {
		a[op[k].loc] = cp;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++) {
		int v;
		cin >> v;
		op[v].son.push_back(i);
		cin >> op[i].type >> op[i].loc;
		if(op[i].type == 1) {
			cin >> op[i].val;
		}
		else {
			op[i].ans = ++k;
		}
	}
	dfs(0);
	for(int i = 1; i <= k; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}