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

56pts

#3

input：

4 5
-869513306 -55515509 -18235282 -850474412 
0 1 1 -371445967
1 1 4 -455963593
0 1 1 -437838418
3 1 3 -212862770
0 2 1

output:

-869513306

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct node{
	int l, r, lc, rc, v;
}tr[N << 6];
int rt[N], a[N];
int cnt, n, T;

int read(){
	char c = getchar();
	int cnt = (c == '-') ? -1 : 1;
	int res = 0;
	while(c < '0' || c > '9'){
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		res = (res << 1) + (res << 3) + (c ^ 48);
		c = getchar();
	}
	return res * cnt;
}

int addnode(int u){
	tr[++cnt] = tr[u];
	return cnt;
}

int make(int l, int r, int a[]){
	int u = ++cnt;
	tr[u].l = l;
	tr[u].r = r;
	if(l == r){
		tr[u].v = a[l];
		return u;
	}
	int mid = (l + r) >> 1;
	tr[u].lc = make(l, mid, a);
	tr[u].rc = make(mid + 1, r, a);
	return u;
}

int _update(int u, int q, int x){
	u = addnode(u);
	if(tr[u].l == tr[u].r){
		tr[u].v = x;
		return u;
	}
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(mid >= q)	tr[u].lc = _update(tr[u].lc, q, x);
	else	tr[u].rc = _update(tr[u].rc, q, x);
	return u;
}

int _query(int u, int q){
	if(tr[u].l == tr[u].r){
		return tr[u].v;
	}
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(mid >= q)	return _query(tr[u].lc, q);
	else	return _query(tr[u].rc, q);	
}

void build(int n, int a[]){
	rt[0] = make(1, n, a);
}

void update(int t, int bef, int q, int x){
	rt[t] = _update(rt[bef], q, x);
}

int query(int t, int bef, int q){
	rt[t] = rt[bef];
	return _query(rt[bef], q);
}

int main(){
	n = read(), T = read();
	for(int i = 1; i <= n; i++){
		a[i] = read();
	}
	build(n, a);
	for(int i = 1; i <= T; i++){
		int bef = read(), op = read(), q = read();
		if(op == 1){
			int x = read();
			update(i, bef, q, x);
		}
		if(op == 2){
			int ans = query(i, bef, q);
			printf("%d\n", ans);
		}
	}
	return 0;
}