Luogu P3919 【模板】可持久化线段树 1（可持久化数组）

板子，正好温习一下主席树的写法
记得数组开 (32) 倍！！

(Code)

#include<cstdio>
using namespace std;

const int N = 1e6 + 5;
int rt[N] , a[N] , n , m , size;
struct Segment{
	int ls , rs , s;
}seg[N << 5];

inline int build(int l , int r)
{
	int o = ++size;
	if (l == r) {seg[o].s = a[l]; return o;}
	int mid = (l + r) >> 1;
	seg[o].ls = build(l , mid) , seg[o].rs = build(mid + 1 , r);
	return o;
}

inline int insert(int u , int x , int val , int l , int r)
{
	int o = ++size; seg[o].ls = seg[u].ls , seg[o].rs = seg[u].rs;
	if (l == r) {seg[o].s = val; return o;}
	int mid = (l + r) >> 1;
	if (x <= mid) seg[o].ls = insert(seg[u].ls , x , val , l , mid);
	else seg[o].rs = insert(seg[u].rs , x , val , mid + 1 , r);
	return o;
}

inline int query(int u , int x , int l , int r)
{
	if (l == r) return seg[u].s;
	int mid = (l + r) >> 1;
	if (x <= mid) return query(seg[u].ls , x , l , mid);
	else return query(seg[u].rs , x , mid + 1 , r);
}

int main()
{
	scanf("%d%d" , &n , &m);
	for(register int i = 1; i <= n; i++) scanf("%d" , a + i);
	rt[0] = build(1 , n);
	int v , op , loc , val;
	for(register int i = 1; i <= m; i++)
	{
		scanf("%d%d%d" , &v , &op , &loc);
		if (op == 2){printf("%d
" , query(rt[v] , loc , 1 , n)) , rt[i] = rt[v];}
		else {scanf("%d" , &val) , rt[i] = insert(rt[v] , loc , val , 1 , n);}
	}
}