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
| #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]; } } }
|