可持久化数组

可持久化数组

题意

主席树板子题。

解法

没什么可说的。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#define INF 2139062143
#define MAX 0x7ffffffffffffff
#define del(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T&x)
{
    x=0;T k=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;
}
const int maxn=1e6+5;
int root[maxn];
struct node{
	int lc,rc;
	ll sum;
}T[maxn*60];
int sz=0;

void update(int l,int r,int pos,ll val,int &x,int y){
	T[++sz]=T[y],T[sz].sum=val,x=sz;
	if(l==r) return;
	int mid=(l+r)/2;
	if(pos<=mid) update(l,mid,pos,val,T[x].lc,T[y].lc);
	else update(mid+1,r,pos,val,T[x].rc,T[y].rc);
}

ll query(int l,int r,int pos,int x){
	if(l==r) return T[x].sum;
	int mid=(l+r)/2;
	if(pos<=mid) return query(l,mid,pos,T[x].lc);
	else return query(mid+1,r,pos,T[x].rc);
}
int n,m;
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) {
		ll k;
		read(k);
		update(1,n,i,k,root[0],root[0]);
	}
	int v,key,pos;
	ll val;
	for(int i=1;i<=m;i++) {
		read(v),read(key);
		if(key==1){
			read(pos),read(val);
			update(1,n,pos,val,root[i],root[v]);
		}
		else{
			read(pos);
			printf("%lld
",query(1,n,pos,root[v]));
			root[i]=root[v];
		}
	}
	return 0;
}