主席树求调

P3919 【模板】可持久化线段树 1(可持久化数组)

已解决,将PST定义的build、upd里面所有xx变量改成局部变量
by YoungL @ 2024-01-16 13:44:18


完整代码: ```cpp #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; inline int build(int l, int r) { int xx; // 不能用全局变量,否则递归后会被更改 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) { int xx; 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; } ```
by YoungL @ 2024-01-16 13:45:23


@[YoungL](/user/1050683) 已解决,谢谢
by Br00k5xx @ 2024-01-18 14:58:02


|