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

[$\frak{Link}$Link]

---

被暗算了， MAXN 一开始开成了 2*10^5
RE 了半天，哭辽
我恰柠檬了

---

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define getchar() (frS==frT&&(frT=(frS=frBB)+fread(frBB,1,1<<12,stdin),frS==frT)?EOF:*frS++)
char frBB[1<<12], *frS=frBB, *frT=frBB;
int read()
{
	int x = 0; bool w = 0; char ch = getchar();
	while (!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
	return w?-x:x;
}
const int MAXN = 1000005;
const int MAXS = 22 * MAXN;
int n, m, tot = 0, a[MAXN], Rt[MAXN], Seg[MAXS], LC[MAXS], RC[MAXS];
void modify(int &cur, int Pos, int L, int R, const int &idid, const int &tarval)
{
	cur = ++tot; LC[cur] = LC[Pos]; RC[cur] = RC[Pos];
	if (L == R) { Seg[cur] = tarval; return;}
	int Mid = L + R >> 1;
	if (idid <= Mid) modify(LC[cur], LC[Pos], L, Mid, idid, tarval);
	else modify(RC[cur], RC[Pos], Mid + 1, R, idid, tarval);
}
int chk(int Pos, int L, int R, const int &idid)
{
	if (L == R) return Seg[Pos];
	int Mid = L + R >> 1;
	if (idid <= Mid) return chk(LC[Pos], L, Mid, idid);
	else return chk(RC[Pos], Mid + 1, R, idid);
}
void Build(int &Pos, int L, int R)
{
	Pos = ++tot;
	if (L == R) { Seg[Pos] = a[L]; return;}
	int Mid = L + R >> 1;
	Build(LC[Pos], L, Mid), Build(RC[Pos], Mid + 1, R);
}
int main()
{
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	Build(Rt[0], 1, n);
	for (int ver, typ, loc, val, i = 1; i <= m; ++i)
	{
		ver = read(); typ = read(); loc = read();
		if (typ == 1) { val = read(); modify(Rt[i], Rt[ver], 1, n, loc, val);}
		else printf("%d\n", chk(Rt[i] = Rt[ver], 1, n, loc));
	}
	return 0;
}