题目传送门

sol:在洛谷上看到一种dfs + 离线的方法，可以解决大部分可持久化问题。把依赖关系看成边，然后建树。这样本来要解决的多个版本只要在一个版本上进行修改就好了。

离线 + dfs

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int MAXN = 1e6 + ;

vector<int> edge[MAXN];

int a[MAXN], b[MAXN], c[MAXN], d[MAXN];

int ans[MAXN];

void dfs(int u) {

    int tmp = a[c[u]];

    if (b[u] == ) a[c[u]] = d[u];

    else ans[u] = tmp;

    for (auto v : edge[u]) dfs(v);

    a[c[u]] = tmp;

}

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    for (int i = ; i <= m; i++) {

        int fa; scanf("%d", &fa);

        edge[fa].push_back(i);

        scanf("%d%d", &b[i], &c[i]);

        if (b[i] == ) scanf("%d", &d[i]);

    }

    dfs();

    for (int i = ; i <= m; i++) {

        if (b[i] == )

            printf("%d\n", ans[i]);

    }

    return ;

}

巴特西

洛谷-P3919-可持久化数组

题目传送门

最新文章

热门文章