P3919 【模板】可持久化数组——可持久化线段树

P3919 【模板】可持久化数组——可持久化线段树

#include #include #include #include using namespace std;const int maxn = 1e6 + 10;const int maxm = 2e7 + 10;int sz;int head[maxn];struct Node { int l, r, val;}node[maxm];void build(int &root, int l, int r) { root = ++sz; if (l == r) { scanf("%d", &node[root].val); } else { int mid = (l + r) >> 1; build(node[root].l, l, mid); build(node[root].r, mid+1, r); }}void update(int *root, int old, int l, int r, int p, int val) { while (l != r) { *root = ++sz; int mid = (l + r) >> 1; if (p <= mid) { r = mid; node[*root].r = node[old].r; root = &node[*root].l; old = node[old].l; } else { l = mid + 1; node[*root].l = node[old].l; root = &node[*root].r; old = node[old].r; } } node[(*root = ++sz)].val = val;}int query(int root, int l, int r, int p) { while (l != r) { int mid = (l + r) >> 1; if (p <= mid) { r = mid; root = node[root].l; } else { l = mid + 1; root = node[root].r; } } return node[root].val;}int main() { int n, m; scanf("%d%d", &n, &m); build(head[0], 1, n); for (int i = 1; i <= m; i++) { int v, op, loc; scanf("%d%d%d", &v, &op, &loc); if (op == 1) { int val; scanf("%d", &val); update(&head[i], head[v], 1, n, loc, val);// cout << head[i] << "++" << endl; } else { printf("%d\n", query(head[v], 1, n, loc)); head[i] = ++sz; node[sz].l = node[head[v]].l; node[sz].r = node[head[v]].r; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。