CF2026F 题解

这也太牛了。

只考虑查询的话是个朴素的 01 背包问题，但是前面有各种奇怪的修改，貌似不好解决。

首先将“新开连锁店”的操作解决。这里可以使用 可持久化并查集 中的技巧，将所有版本建成一棵树，在树上跑搜即可。这样就只需支持撤销。

题目剩下两种操作又是从两种方向修改，要支持头尾插入撤销。我们知道 01 背包是容易支持撤销的，所以朴素的想法是维护两个栈，一个负责头一个负责尾，分别维护自身的 01 背包，查询时可以将两个背包的这一单点 O(V) 合并。

那一个栈空了怎么办呢？参考 C++ 中的 deque 是怎么维护的。它的底层是两个 vector，一个被删空时会将满的那边分一半过去，复杂度是均摊 O(n) 的。证明也很简单：分一半过去之后两个栈的地位平等，我们可以直接认为每个元素只会被从头栈扔到尾栈恰好一次，故复杂度为 O(n)。并且重新背包时的复杂度和分过去的元素个数是等同的，所以 dp 也只会跑 O(n) 遍。

总时间复杂度 O(nV)，可以通过。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e4 + 10;
const int MAXM = 2e3 + 10;

vector<pair<int, int>> G[MAXN], q[MAXN]; vector<int> af, ag;

int rt[MAXN], p[MAXN], t[MAXN], tf, tg, tot, cnt, tp, tq;

int n, f[MAXN][MAXM], g[MAXN][MAXM], ans[MAXN];

inline 
void addf(int x) {
    af.emplace_back(x), tf++, memcpy(f[tf], f[tf - 1], sizeof f[tf - 1]);
    for (int i = 2e3; i >= p[x]; i--) f[tf][i] = max(f[tf - 1][i], f[tf - 1][i - p[x]] + t[x]);
    for (int i = 1; i <= 2e3; i++) f[tf][i] = max(f[tf][i], f[tf][i - 1]);
}

inline 
void addg(int x) {
    ag.emplace_back(x), tg++, memcpy(g[tg], g[tg - 1], sizeof g[tg - 1]);
    for (int i = 2e3; i >= p[x]; i--) g[tg][i] = max(g[tg][i], g[tg - 1][i - p[x]] + t[x]);
    for (int i = 1; i <= 2e3; i++) g[tg][i] = max(g[tg][i], g[tg][i - 1]);
}

inline 
void rebuild(bool t) {
    vector<int> tmp;
    for (int x : af) tmp.emplace_back(x);
    reverse(tmp.begin(), tmp.end());
    for (int x : ag) tmp.emplace_back(x);
    int x = (tmp.size() + t) >> 1; tf = tg = 0, af.clear(), ag.clear();
    for (int i = x - 1; ~i; i--) addf(tmp[i]);
    for (int i = x; i < tmp.size(); i++) addg(tmp[i]);
}

inline 
int delf() {
    if (af.empty()) rebuild(1);
    int x = af.back(); return af.pop_back(), tf--, x;
}

inline 
int delg() {
    if (ag.empty()) rebuild(0);
    int x = ag.back(); return ag.pop_back(), tg--, x;
}

inline 
int ask(int x) {
    int ans = 0;
    for (int i = 0; i <= x; i++) ans = max(ans, f[tf][i] + g[tg][x - i]);
    return ans;
}

void dfs(int u) {
    for (pair<int, int> x : q[u]) ans[x.second] = ask(x.first);
    for (pair<int, int> x : G[u]) {
        int v = x.first, w = x.second;
        if (w) addg(w), dfs(v), delg();
        else w = delf(), dfs(v), addf(w);
    }
}

int main() {
    scanf("%d", &n), rt[1] = tot = cnt = 1;
    for (int i = 1, op, x, y; i <= n; i++) {
        scanf("%d%d", &op, &x);
        if (op == 1) rt[++cnt] = rt[x];
        if (op == 2) {
            tp++, scanf("%d%d", &p[tp], &t[tp]);
            G[rt[x]].emplace_back(++tot, tp), rt[x] = tot;
        }
        if (op == 3) G[rt[x]].emplace_back(++tot, 0), rt[x] = tot;
        if (op == 4) scanf("%d", &y), q[rt[x]].emplace_back(y, ++tq);
    }
    dfs(1);
    for (int i = 1; i <= tq; i++) printf("%d\n", ans[i]);
}