样例输出了

0
0
0
0
88
0

代码

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define ls t[x].l
#define rs t[x].r
#define val t[x].v
using namespace std;
int n, m, a[1000005];
struct PST
{
    struct node
    {
        int l, r, v;
    } t[20000005];
    int rt[20000005], sz = 0, tp = 0, xx;
    inline int build(int l, int r)
    {
        xx = ++sz;
        if (l == r)
        {
            t[xx].v = a[l];
            return xx;
        }
        t[xx].l = build(l, mid);
        t[xx].r = build(mid + 1, r);
        return xx;
    }
    inline int qry(int x, int l, int r, int g)
    {
        if (l == r)
            return val;
        if (g <= mid)
            return qry(ls, l, mid, g);
        else
            return qry(rs, mid + 1, r, g);
    }
    inline int upd(int x, int l, int r, int g, int v)
    {
        if (l == r)
        {
            t[++sz].v = v;
            return sz;
        }
        if (g <= mid)
        {
            xx = upd(ls, l, mid, g, v);
            t[++sz].l = xx;
            t[sz].r = rs;
            return sz;
        }
        else
        {
            xx = upd(rs, mid + 1, r, g, v);
            t[++sz].l = ls;
            t[sz].r = xx;
            return sz;
        }
    }
} tree;
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    tree.rt[0] = tree.build(1, n);
    int v, op, loc, value;
    while (m--)
    {
        scanf("%d %d %d", &v, &op, &loc);
        if (op == 1)
        {
            scanf("%d", &value);
            tree.rt[++tree.tp] = tree.upd(tree.rt[v], 1, n, loc, value);
        }
        else
        {
            tree.rt[++tree.tp] = tree.rt[v];
            printf("%d\n", tree.qry(tree.rt[v], 1, n, loc));
        }
    }
    return 0;
}