闲人免进

起名字重要吗 · 2024-07-12 15:41:29 · 个人记录

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m,rt,op,root[N],id,a[N];
struct node {
    int l,r,val;
} t[N];
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*10+ch-48,ch=getchar();
    return x*f;
}
inline void write(int x) {
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int build(int x,int l,int r) {
    x=++id;
    if(l==r) {
        t[x].val=a[l];
        return id;
    }
    int mid=(l+r)/2;
    t[x].l=build(t[x].l,l,mid);
    t[x].r=build(t[x].r,mid+1,r);
    return x;
}
int newnode(int x) {
    t[++id]=t[x];
    return id;
}
int update(int x,int l,int r,int k,int val) {
    int X=newnode(x);
    if(l==r) {
        t[X].val=val;
    } else {
        int mid=(l+r)/2;
        if(k<=mid) {
            t[X].l=update(t[x].l,l,mid,k,val);
        } else {
            t[X].r=update(t[x].r,mid+1,r,k,val);
        }
    }
    return X;
}
int query(int x,int l,int r,int k) {
    if(l==r) {
        return t[x].val;
    } else {
        int mid=(l+r)/2;
        if(k<=mid) {
            return query(t[x].l,l,mid,k);
        } else {
            return query(t[x].r,mid+1,r,k);
        }
    }
}
int main() {
    n=read();
    m=read();
    int x,y;
    for(int i=1; i<=n; i++) {
        a[i]=read();
    }
    root[0]=build(0,1,n);
    for(int i=1; i<=m; i++) {
        rt=read();
        op=read();
        x=read();
        if(op==1) {
            y=read();
            root[i]=update(root[rt],1,n,x,y);
        } else {
            write(query(root[rt],1,n,x));
            puts("");
            root[i]=root[rt];
        }
    }
    return 0;
}