rt

样例的最后一次询问都过不去（

#include<bits/stdc++.h>
#define N 2000006
#define INF 2000000005
using namespace std;
int a[N],n,bh,t,r[N];
struct tree{
    int lc[N<<2],rc[N<<2],num[N<<2];
    inline void build(int &no,int l,int r){
        no=++bh;
        if(l==r){ num[no]=a[l]; return ;}
        int mi=l+r>>1;
        build(lc[no],l,mi),build(rc[no],mi+1,r);
    }
    inline void ins(int &no,int pre,int l,int r,int pl,int k){
        if(l>pl||r<pl) return ;
        no=++bh,lc[no]=lc[pre],rc[no]=rc[pre];
        if(l==r){ num[no]=k; return ;}
        int mi=l+r>>1;
        ins(lc[no],no,l,mi,pl,k),ins(rc[no],no,mi+1,r,pl,k);
    }
    inline int qur(int no,int l,int r,int pl){
        if(l>pl||r<pl) return INF;
        if(l==r) return num[no];
        int mi=l+r>>1,num=qur(lc[no],l,mi,pl);
        if(num==INF) return qur(rc[no],mi+1,r,pl);
        return num;
    }
}tr;
signed main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    tr.build(r[0],1,n);
    for(int i=1,pre,op,pl,val;i<=t;++i){
        scanf("%d%d%d",&pre,&op,&pl);
        if(op&1) scanf("%d",&val),tr.ins(r[i],r[pre],1,n,pl,val);
        else printf("%d\n",tr.qur(r[pre],1,n,pl)),r[i]=r[pre];
    }
    return 0;
}