Luogu P3919 [模板]可持久化线段树___主席树

题目大意：

给出长度为 n n n的序列， m m m次操作，
操作包括
1.回到前面某个版本，将该版本中的某个数修改后，将修改的版本作为该操作后的新版本
2.回到前面某个版本，查询该版本中序列的第k个数，并将该版本复制作为该搞作后的新版本（完全相同）

n , m < = 1 e 6 n,m<=1e6 n,m<=1e6
修改前后任意序列中的数， − 1 0 9 < -10^9< −109<数值 < 1 0 9 <10^9 <109

分析：

对整个序列的编号 1 到 n 1到n 1到n建立主席树，
每次在新版本建的新树链的叶子节点上打上对应的修改数值作为标记
注意对于操作2而言，虽然是查询，但是查询的历史版本可作为当前操作编号的版本

代码：

#include<bits/stdc++.h>

#define N 1000005

using namespace std;

int ls[N*20], rs[N*20], val[N*20], rot[N], a[N];
int n, m, cnt, tot;

void read(int &x) {
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x*10+(s-'0'); s = getchar(); }  
	x = x*f;
}

int Build(int L, int R) {
	int now = ++cnt;
	if (L == R) { val[now] = a[L]; return now; }
	int mid = (L+R)>>1;
	if (L < R) {
		ls[now] = Build(L, mid);
		rs[now] = Build(mid+1, R);
	}
	return now;
}

void Insert(int cdp, int cdq, int pos, int num) {
	rot[cdp] = ++cnt;
	int now1 = rot[cdq];
	int now2 = rot[cdp];
	int L = 1, R = n;
	for (; ls[now1] || rs[now1];) {
		int mid = (L+R)>>1;
		if (pos <= mid) {
			rs[now2] = rs[now1]; ls[now2] = ++cnt;
			now1 = ls[now1]; 
			now2 = ls[now2];
			R = mid;
		} else {
			ls[now2] = ls[now1]; rs[now2] = ++cnt;
			now1 = rs[now1];
			now2 = rs[now2];
			L = mid+1;
		}
	}
	val[cnt] = num;
}

void change(int now, int L, int R, int pos, int num) {
	if (L == R) { val[now] = num; return; }
	int mid = (L+R)>>1;
	if (pos <= mid) change(ls[now], L, mid, pos, num); 
	   else change(rs[now], mid+1, R, pos, num);
}

int Getanswer(int now, int L, int R, int pos) {
	if (L == R) return val[now];
	int mid = (L+R)>>1; 
	if (pos <= mid) return Getanswer(ls[now], L, mid, pos); 
	   else return Getanswer(rs[now], mid+1, R, pos);
}


int main() {
	freopen("data.in", "r", stdin);
	read(n); read(m);
	for (int i = 1; i <= n; i++) read(a[i]);
	rot[0] = Build(1, n);
	tot = 0;
	int lst, opt, pos, num;
	for (int ask = 1; ask <= m; ask++) {
		read(lst), read(opt), read(pos);
		if (opt == 1) read(num), Insert(ask, lst, pos, num); 
		 else rot[ask] = rot[lst], printf("%d\n", Getanswer(rot[lst], 1, n, pos));
	}
	return 0;
}