1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include<bits/stdc++.h> const int N=1000005; using namespace std; int a[N],n,q,rt[N*20]; #define MAXB 50000000 char buf[MAXB],*cp=buf; inline int read() { int f=1,x=0; while(*cp<'0'||*cp>'9') { if(*cp=='-') f=-1; cp++; } while(*cp>='0'&&*cp<='9') { x=x*10+*cp-'0'; cp++; } return f*x; } struct Persistable_Segment_Tree { int lc[N*20],rc[N*20],val[N*20],cnt; inline void build(int &o,int l,int r){ o=++cnt; if(l==r) { val[o]=a[l]; return; } int mid=(l+r)>>1; build(lc[o],l,mid); build(rc[o],mid+1,r); } inline void ins(int &o,int pre,int l,int r,int q,int v){ o=++cnt; lc[o]=lc[pre]; rc[o]=rc[pre]; val[o]=val[pre]; if(l==r) { val[o]=v; return; } int mid=(l+r)>>1; if(q<=mid) ins(lc[o],lc[pre],l,mid,q,v); else ins(rc[o],rc[pre],mid+1,r,q,v); } inline int query(int o,int l,int r,int q){ if(l==r) return val[o]; int mid=(l+r)>>1; if(q<=mid) return query(lc[o],l,mid,q); else return query(rc[o],mid+1,r,q); } }T; int main() { fread(buf,1,MAXB,stdin); n=read(); int m=read(); for(int i=1;i<=n;i++) a[i]=read(); T.build(rt[0],1,n); for(int i=1;i<=m;i++){ int pre=read(),opt=read(),x=read(); if(opt==1) { int v=read(); T.ins(rt[i],rt[pre],1,n,x,v); } if(opt==2) { printf("%d\n",T.query(rt[pre],1,n,x)); rt[i]=rt[pre]; } } }
|