Steven_Meng's Blog

传送门

用可持久化线段树实现，$rt[i]$表示每个副本线段树的根节点。

#include <bits/stdc++.h>
#define MAXN 1000005
#define MAXM 30
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int val;//每个节点的权值（只有叶节点有）
    }tree[MAXN*MAXM];
    int tot;
    void Build(int &i,int L,int R){
        i=++tot;
        if (L==R){
            tree[i].val=a[L];
            return ;
        }
        int mid=(L+R)>>1;
        Build(tree[i].l,L,mid);
        Build(tree[i].r,mid+1,R);
    }
    void Update(int &i,int his,int pos,int val,int L,int R){
        i=++tot;
        tree[i].l=tree[his].l,tree[i].r=tree[his].r,tree[i].val=tree[his].val;
        if (L==R){
            tree[i].val=val;
            return ;
        }
        int mid=(L+R)>>1;
        if (pos<=mid) Update(tree[i].l,tree[his].l,pos,val,L,mid);
        else Update(tree[i].r,tree[his].r,pos,val,mid+1,R);
    }
    int Query(int i,int pos,int L,int R){
        if (L==R) return tree[i].val;
        int mid=(L+R)>>1;
        if (pos<=mid) return Query(tree[i].l,pos,L,mid);
        else return Query(tree[i].r,pos,mid+1,R);
    }
}
using namespace SegmentTree;
int rt[MAXN];
int main(){
    int n=read(),q=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    Build(rt[0],1,n);
    for (register int i=1;i<=q;++i){
        int v=read(),opr=read(),loc=read();
        if (opr==1){
            int val=read();
            Update(rt[i],rt[v],loc,val,1,n);
        }
        else if (opr==2){
            printf("%d\n",Query(rt[v],loc,1,n));
            rt[i]=rt[v];
        }
    }
}