[题解]LuoGu3919：【模板】可持久化数组（可持久化线段树/平衡树）

原题传送门
用主席树做啊
首先想到暴力，然后用主席树优化空间
每次比之前会多log个点，空间上还过得去

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct chairman{
	int l, r, v;
}seg[maxn << 5];
int rt[maxn], sz, n, m, a[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void build(int &rt, int l, int r){
	rt = ++sz;
	if (l == r){
		seg[rt].v = a[l]; return;
	}
	int mid = (l + r) >> 1;
	build(seg[rt].l, l, mid); build(seg[rt].r, mid + 1, r);
}

int update(int o, int l, int r, int p, int k){
	int oo = ++sz;
	seg[oo] = seg[o];
	if (l == r){
		seg[oo].v = k; return oo;
	}
	int mid = (l + r) >> 1;
	if (mid >= p) seg[oo].l = update(seg[oo].l, l, mid, p, k); else
	seg[oo].r = update(seg[oo].r, mid + 1, r, p, k);
	return oo;
}

int query(int rt, int l, int r, int p){
	if (l == r) return seg[rt].v;
	int mid = (l + r) >> 1;
	if (mid >= p) return query(seg[rt].l, l, mid, p); else
	return query(seg[rt].r, mid + 1, r, p);
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	build(rt[0], 1, n);
	for (int i = 1; i <= m; ++i){
		int x = read(), opt = read(), y = read();
		if (opt == 1){
			int z = read();
			rt[i] = update(rt[x], 1, n, y, z);
		} else{
			rt[i] = rt[x];
			printf("%d\n", query(rt[i], 1, n, y));
		}
	}
	return 0;
}