求调

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+1,M=N*24;
struct SegmentTreeNode{
    int l,r,ls,rs,val;
    SegmentTreeNode(int l=0,int r=0,int ls=0,int rs=0,int val=0)
        :l(l),r(r),ls(ls),rs(rs),val(val){}
}f[M];
int n,q,a[N],root[N],tot;
void build(int l,int r,int&cur){
    cur=(++tot);
    if(l==r){
        f[cur]=SegmentTreeNode(l,r,0,0,a[l]);//只有叶子结点储存信息
        return;
    }
    int mid=(l+r)>>1;
    f[cur]=SegmentTreeNode(l,r,0,0,0);
    return build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);//建子树
}
void modify(int k,int val,int&cur,int last){
    f[cur=(++tot)]=f[last];//出使化为上个版本
    if(f[cur].l==f[cur].r){
        f[cur].val=val;
        return;
    }//只修改值
    int mid=(f[cur].l+f[cur].r)>>1;
    if(k<=mid)
        modify(k,val,f[cur].ls,f[last].ls);
    else
        modify(k,val,f[cur].rs,f[last].rs);//更新其中一半
    return;
}
int query(int k,int cur){
    if(f[cur].l==f[cur].r)
        return f[cur].val;//叶子
    int mid=(f[cur].l+f[cur].r)>>1;
    if(k<=mid)
        return query(k,f[cur].ls);
    else
        return query(k,f[cur].rs);//其他
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,root[0]);//出使版本0
    for(int op,v,k,val,kase=1;q;--q,kase++){
        cin>>v>>op>>k;
        if(op==1){
            cin>>val;
            modify(k,val,root[kase],root[v]);//更新
        }
        else{
            root[kase]=root[kase-1];//复制版本
            cout<<query(k,root[v])<<'\n';//查询
        }
    }
    return 0;
}