洛谷 - P3919 可持续化数组

传送门：洛谷 - P3919

题目描述

维护两个操作：

1. 在某个历史版本修改某个值
2. 查询某个历史版本的一个值

每进行一次操作，就会生成一个新的版本

输入描述

第一行包含两个整数$N$,$M$，分别表示数组长度和操作个数
第二行包含$N$个数，表示初始数组
接下来$M$行：

1. $v_i$ $1$ $pos$ $val$ 表示在$v_i$个版本的$pos$位置上更改值为$val$
2. $v_i$ $2$ $pos$ 表示在$v_i$个版本查询$pos$位置上的值

输出描述

输出答案

思路分析

主席树维护普通线段树

样例输入

5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

样例输出

59
87
41
87
88
46

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;

inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}


struct node {
    int l, r, val;
} tree[N << 5];

int cnt, root[N], a[N];

void build(int l, int r, int &x) {
    x = ++cnt;
    if (l == r) {
        tree[x].val = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(l, mid, tree[x].l);
    build(mid + 1, r, tree[x].r);
}

inline void update(int l, int r, int ver, int &x, int pos, int v) {
    x = ++cnt;
    tree[x] = tree[ver];
    if (l == r) {
        tree[x].val = v;
        return ;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
        update(l, mid, tree[ver].l, tree[x].l, pos, v);
    else
        update(mid + 1, r, tree[ver].r, tree[x].r, pos, v);
}

inline int query(int x, int l, int r, int pos) {
    if (l == r)
        return tree[x].val;
    int mid = l + r >> 1;
    if (pos <= mid)
        return query(tree[x].l, l, mid, pos);
    else
        return query(tree[x].r, mid + 1, r, pos);
}

int main() {

#ifdef xiaofan
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif

    int n, m, ver, opt, x, y;
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    build(1, n, root[0]);
    for (int i = 1; i <= m; i++) {
        ver = read();
        opt = read();
        switch (opt) {
        case 1:
            x = read();
            y = read();
            update(1, n, root[ver], root[i], x, y);
            break;
        case 2:
            x = read();
            printf("%d\n", query(root[ver], 1, n, x));
            root[i] = root[ver];
            break;
        }
    }




    return 0;
}