题解 P3919 【【模板】可持久化数组（可持久化线段树/平衡树）】

Elegia · 2018-01-10 14:13:51 · 题解

虽然这违反了模板的本意，但是本人认为这种做法也会对应于一类特别的题目。即考虑离线做法。

考虑到每一个版本都被一些版本所依赖，这种依赖关系可以被当做一棵树。在读入时建树，最后进行操作时就是将树从原点0处进行dfs。

对于询问直接存进答案数组，对于修改操作，进行修改后再dfs，结束后再撤回修改。

这种思路可以过掉部分题目，但前提是操作可逆，所以不能过掉诸如可持久化并查集的题目。

#include <cstdio>

using namespace std;

struct edge {
    int v;
    edge* next;
};

const int N = 1000010;

int n, m;
int a[N], ans[N], op[N], k[N], x[N];
edge* g[N];

void add_edge(int u, int v);
void dfs(int u);

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    op[0] = 2;
    for (int i = 1; i <= m; ++i) {
        int v;
        scanf("%d%d%d", &v, &op[i], &k[i]);
        if (op[i] == 1)
            scanf("%d", &x[i]);
        add_edge(v, i);
    }
    dfs(0);
    for (int i = 1; i <= m; ++i)
        if (op[i] == 2)
            printf("%d\n", ans[i]);
    return 0;
}

void dfs(int u) {
    if (op[u] == 2) {
        ans[u] = a[k[u]];
        for (edge* p = g[u]; p; p = p->next)
            dfs(p->v);
    } else {
        int ori = a[k[u]];
        a[k[u]] = x[u];
        for (edge* p = g[u]; p; p = p->next)
            dfs(p->v);
        a[k[u]] = ori;
    }
}

void add_edge(int u, int v) {
    static edge pool[N];
    static edge* p = pool;
    p->v = v;
    p->next = g[u];
    g[u] = p;
    ++p;
}