这是记录：https://www.luogu.com.cn/record/99672057

这是代码，再改真的和题解一模一样了……

#include <bits/stdc++.h>
#define JS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int M = 1e6 + 1;

struct Node {
	int l, r, val;
} T[M * 30];

int n, m, a[M], root[M * 30], rt, op, va, vb, top;

int clone(int x) {
	top++;
	T[top] = T[x];
	return top;
}

int build(int x, int begin, int end) {
	x = ++top;
	if (begin == end) {
		T[x].val = a[begin];
		return top;
	}
	int mid = (begin + end) >> 1;
	T[x].l = build(T[x].l, begin, mid);
	T[x].r = build(T[x].r, mid + 1, end);
	return x;
}

int update(int x, int begin, int end, int c, int val) {
	x = clone(x);
	if (begin == end) {
		T[x].val = val;
	} else {
		int mid = (begin + end) >> 1;
		if (c <= mid) {
			T[x].l = update(T[x].l, begin, mid, c, val);
		} else {
			T[x].r = update(T[x].l, mid + 1, end, c, val);
		}
	}
	return x;
}

int query(int x, int begin, int end, int c) {
	if (begin == end) {
		return T[x].val;
	} else {
		int mid = (begin + end) >> 1;
		if (c <= mid) {
			return query(T[x].l, begin, mid, c);
		} else {
			return query(T[x].r, mid + 1, end, c);
		}
	}
}

int main() {
	JS;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	root[0] = build(0, 1, n);
	for (int i = 1; i <= m; i++) {
		cin >> rt >> op >> va;
		if (op == 1) {
			cin >> vb;
			root[i] = update(root[rt], 1, n, va, vb);
		} else {
			cout << query(root[rt], 1, n, va) << '\n';
			root[i] = root[rt];
		}
	}
	return 0;
}