rt.求调awa /thx

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
#define isdigit(x) (x>='0')
#define gc getchar_unlocked
#define pc(x) putchar_unlocked(x)
template <typename T>
void read(T &x) {
    x=0;
    T fl=1;
    char ch=gc();
    for(;!isdigit(ch);ch=gc()) if(ch=='-') fl=-1;
    for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
    x=x*fl;
}
template <typename T>
void write(T x,char ch) {
    if(x<0) pc('-'),x=-x;
    static int st[20];
    int top=0;
    do {
        st[top++]=x%10;
        x/=10;
    }while(x);
    while(top) pc(st[--top]^48);
    pc(ch);
}
typedef long long ll;
const int N=1e6+7;
int n,m,a[N];
int t,op,x,val;
int rt[N];
struct segtree {
    struct node {
        int val,ls,rs;
    }tr[N<<4];
    int cnt;
    void build(int &u,int l,int r) {
        u=++cnt;
        if(l==r) { tr[u].val=a[l]; return; }
        int mid=(l+r)>>1;
        build(tr[u].ls,l,mid), build(tr[u].rs,mid+1,r);
    }
    void update(int &u,int v,int l,int r,int x,int val) {
        u=++cnt;
        tr[u]=tr[v];
        if(l==r) { tr[u].val=val; return; }
        int mid=(l+r)>>1;
        if(x<=mid) update(tr[u].ls,tr[v].ls,l,mid,x,val);
        else update(tr[u].rs,tr[v].rs,mid+1,r,x,val);
    }
    int query(int u,int l,int r,int x) {
        if(l==r) return tr[u].val;
        int mid=(l+r)>>1;
        if(x<=mid) return query(tr[u].ls,l,mid,x);
        return query(tr[u].rs,mid+1,r,x);
    }
}T;
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    read(n),read(m);
    rep(i,1,n) read(a[i]);
    T.build(rt[0],1,n);
    rep(i,1,m) {
        read(t),read(op);
        if(op==1) {
            read(x),read(val);
            T.update(rt[i],rt[t],1,n,x,val);
        }else{
            read(x);
            rt[i]=rt[t];
            write(T.query(rt[i],1,n,x),'\n');
        }
    }
}