RT，开 O2 就炸了

#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace solve_sbtsk1{

	bool st;

	int n, m, a[9000001];

	class PersistentTree{
		
		public:
		
			struct node{
				int l, r, lp, rp, val;
			} tree[9000001];
			
			int cnt = 0, tot = 0, ver[9000001];
			
			int save_ver(int rt){
				ver[++tot] = rt;
			}
			int get_ver(int x){
				return ver[x];
			}
			
			int build(int l, int r){
				int ind = cnt++;
				tree[ind].l = l, tree[ind].r = r;
				if(l == r){
					tree[ind].val = a[l];
					return ind;
				}
				int mid = (l + r) >> 1;
				tree[ind].lp = build(l, mid);
				tree[ind].rp = build(mid + 1, r);
				return ind;
			}
			int mod(int x, int y, int k){
				int ind = cnt++;
				tree[ind].l = tree[x].l, tree[ind].r = tree[x].r;
				if(tree[ind].l == tree[ind].r){
					tree[ind].val = k;
					return ind;
				}
				int mid = (tree[ind].l + tree[ind].r) >> 1;
				if(y <= mid)
					tree[ind].lp = mod(tree[x].lp, y, k);
				else
					tree[ind].rp = mod(tree[x].rp, y, k);
				return ind;
			}
			int query(int x, int y){
				if(tree[x].l == tree[x].r)
					return tree[x].val;
				int mid = (tree[x].l + tree[x].r) >> 1;
				if(y <= mid)
					return query(tree[x].lp, y);
				else
					return query(tree[x].rp, y);
			}
	}pt;	
	double solve(int testcase, ...){
		
		double used_time = clock();
		
		scanf("%lld%lld", &n, &m);
		for(int i = 1; i <= n; i++){
			scanf("%lld", a + i);
		}
		pt.ver[0] = pt.build(1, n);
		for(int i = 1; i <= m; i++){
			int v, op, x, y;
			scanf("%lld%lld%lld", &v, &op, &x);
			if(op == 1){
				scanf("%lld", &y);
				pt.save_ver(pt.mod(pt.get_ver(v), x, y));
			}
			else{
				printf("%lld\n", pt.query(pt.get_ver(v), x));
				pt.save_ver(pt.mod(pt.get_ver(v), x, y));
			}
		}
		
		return clock() - used_time;
	}
	
	bool ed;
};

signed main(){

#ifndef ONLINE_JUDGE
	printf("Used time %.0lfms.\n", solve_sbtsk1::solve(1, "local"));
	printf("Used memory %lldmb.\n", (&solve_sbtsk1::ed - &solve_sbtsk1::st) / 1048576LL);
#else
	solve_sbtsk1::solve(1, ONLINE_JUDGE);	
#endif
	return 0;
}