初学主席树，8pts求条（玄关）

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=4e7;
inline int read(){
	char ch; int f = 1,res = 0; ch = getchar();
	while (!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {res = res * 10 + (ch - '0'); ch = getchar();}
	return res;
}
int n,q,a[maxn],root[maxn],tot=0;
struct node{
	int ls,rs,val;
}tree[maxn];

int newnd(int id){
	tot++; tree[tot] = tree[id];
	return tot;
}

int mktr(int id,int L,int R){
	tot++; id = tot;
	if (L == R){
		tree[id].val = a[L]; return tot;
	}
	int mid = (L + R) / 2;
	tree[id].ls = mktr(tree[id].ls,L,mid);
	tree[id].rs = mktr(tree[id].rs,mid + 1,R);
	return id;
}

int update(int id,int L,int R,int x,int val){
	id = newnd(id);
	if (L == R) tree[id].val = val;
	else{
		int mid = (L + R) / 2;
		if (x <= mid) tree[id].ls = update(tree[id].ls,L,mid,x,val);
		else tree[id].rs = update(tree[id].rs,mid + 1,R,x,val);
	}
	return id;
}

int ask(int id,int L,int R,int x){
	if (L == R) return tree[id].val;
	else{
		int mid = (L + R) / 2;
		if (x <= mid) return ask(tree[id].ls,L,mid,x);
		else return ask(tree[id].rs,mid + 1,R,x);
	}
}

signed main(){
	n = read(); q = read();
	for (int i = 1;i <= n;i++) a[i] = read();
	root[0] = mktr(0,1,n);
	for (int i = 1;i <= q;i++){
		int rt,m,x,y;
		rt = read(); m = read(); x = read();
		if(m == 1){
			y = read(); root[i] = update(root[rt],1,n,x,y);
		}else{
			cout << ask(root[rt],1,n,x) << endl;
			root[i] = root[rt];
		}
	}
	return 0;
}