主席树(历史版本修改与查询)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
const int M=5000005;
int Cnt,n,m,sum[M<<2],root[M],lc[M<<2],rc[M<<2];
int build(int l,int r){
    int t=++Cnt;
    if(l==r){
		scanf("%d",&sum[t]);
        return t;
	}
    int mid=(l+r)>>1;
	lc[t]=build(l,mid);
    rc[t]=build(mid+1,r);
	return t;
}
int modify(int o,int l,int r,int p,int c){
    int oo=++Cnt;
	if(l==r){
		sum[oo]=c;
		return oo;
	}
    lc[oo]=lc[o];
	rc[oo]=rc[o];
    int mid=(l+r)>>1;
    if(p<=mid){
		lc[oo]=modify(lc[oo],l,mid,p,c);
	}
    else{
		rc[oo]=modify(rc[oo],mid+1,r,p,c);
	}
    return oo;
}
int query(int o,int l,int r,int p){
    if(l==r){
        return sum[o];
	}
	int ans,mid=(l+r)>>1;
    if(p<=mid){
		ans=query(lc[o],l,mid,p);
	}
    else{
		ans=query(rc[o],mid+1,r,p);
	}
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
	build(1,n);
	int v,opt,loc,val;
    root[0]=1;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&v,&opt,&loc);
        if(opt==1){
            scanf("%d",&val);
            root[i]=modify(root[v],1,n,loc,val);
        }
        if(opt==2){
            root[i]=root[v];
            printf("%d\n",query(root[v],1,n,loc));
        }
    }
    return 0;
}