蒟蒻代码

#include<set>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>

#define int ll
typedef long long ll;

//================================================================
namespace FastIO
{
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT;
char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;

inline char getChar()
{
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                        (iS == iT ? EOF : *iS++)) : *iS++);
}

void read() {}
void print() {}

inline void flush ()
{
    fwrite (obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
inline void putc (char x)
{
    *oS ++ = x;
    if (oS == oT) flush ();
}

template <typename I, typename ... T>
inline void read (I &x, T &...oth)
{
    c = getChar();
    f = 1;
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = getChar();
    }
    x = 0;
    while (isdigit(c))
    {
        x = x * 10 + c - '0';
        c = getChar();
    }
    x = x * f;
    read(oth...);
}

template <class I, class ... T>
inline void print (I x, T &...oth)
{
    if (!x) putc ('0');
    if (x < 0)
        putc ('-'), x = -x;
    while (x)
        qu[++ qr] = x % 10 + '0',  x /= 10;
    while (qr)
        putc (qu[qr --]);
    //TODO Add Format Control
    putc(char(10));
    print(oth...);
}

struct Flusher_
{
    ~Flusher_()
    {
        flush();
    }
} io_flusher_;
}

//===========================================
constexpr int maxn = 3.2e7 + 100;
constexpr int maxr = 1e6 + 10;

int n, m;
int a[maxr];

struct Segtree
{
    int cnt = 1;
    struct Node
    {
        int val;
        Node *ls = nullptr, *rs = nullptr;
    } data[maxn];
    Node *root[maxr];
    void upd(Node *p)
    {
        p->val = p->ls->val + p->rs->val;
    }
    void build(Node *p, int cl = 1, int cr = n)
    {
        if (cl == cr)
            return p->val = a[cl], void();
        p->ls = data + (++cnt), p->rs = data + (++cnt);
        int mid = (cr + cl) >> 1;
        build(p->ls, cl, mid);
        build(p->rs, mid + 1, cr);
        upd(p);
    }
    void modify(int pos, int val, Node *p, Node *q, int cl = 1, int cr = n)
    {
        if (cl == cr)
            q->val = val;
        else
        {
            q->ls = p->ls, q->rs = p->rs;
            int mid = (cl + cr) >> 1;
            if (pos <= mid)
                q->ls = data + (++cnt), modify(pos, val, p->ls, q->ls, cl, mid);
            else
                q->rs = data + (++cnt), modify(pos, val, p->rs, q->rs, mid + 1, cr);
            upd(q);
        }
    }
    int query(int pos, Node *p, int cl = 1, int cr = n)
    {
        if (cl == cr)
            return p->val;
        int mid = (cl + cr) >> 1;
        if (pos <= mid)
            return query(pos, p->ls, cl, mid);
        else
            return query(pos, p->rs, mid + 1, cr);
    }
} tr;

void getData()
{
    using namespace FastIO;
    read(n, m);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    tr.root[0] = tr.data + 1;
    tr.build(tr.root[0]);
}

void sol()
{
    using namespace FastIO;
    int v, opt, x, y;
    for (int t = 1; t <= m; ++t)
    {
        read(v, opt, x);
        if (opt == 1)
        {
            read(y);
            tr.root[t] = tr.data + (++tr.cnt);
            tr.modify(x, y, tr.root[v], tr.root[t]);
        }
        else
        {
            tr.root[t] = tr.root[v];
            print(tr.query(x, tr.root[t]));
        }
    }
}

signed main()
{
    getData();
    sol();

    return 0;
}