题解：CF601E A Museum Robbery

pldzy · 2025-01-12 16:04:12 · 题解

Happy New Year!

Solution

删除任意编号的存在物品，不强制在线，先扔一个线段树分治上去。

发现是背包，想到猫树。背包是典型的合并复杂度非常高的信息。发现我们能承受的复杂度是加入一个物品的 O(k)，而非合并两个背包的 O(k^2)。

另一个有趣的性质是背包信息支持撤销。

那比起在每个节点维护物品构成的背包，我们选择类似 dfs() 的过程，每次加入物品然后继续递归，回溯的时候撤销即可。算是利用上“保证物品总数不超过 1e4”的条件了。

时间复杂度 O(nk\log q)。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair

const int maxn = 3e4 + 5, maxm = 1e3 + 5;

int n, k, q, op[maxn];
int L[maxn], R[maxn]; pii a[maxn];

vector<pii> t[maxn << 2];

#define ls (x << 1)
#define rs (x << 1 | 1)

inline void updtr(int x, int l, int r, int L, int R, pii v){
    if(l >= L and r <= R) return t[x].push_back(v), void();
    int mid = l + r >> 1;
    if(L <= mid) updtr(ls, l, mid, L, R, v);
    if(R > mid) updtr(rs, mid + 1, r, L, R, v);
}

const ll p = 1e7 + 19, mod = 1e9 + 7;

ll st[maxn][maxm], ans[maxn]; int tp;

inline void qry(int x, int l, int r){
    int tp0 = tp;
    for(auto nw : t[x]){
        ++tp; 
        rep(i, 1, k) 
            st[tp][i] = max(st[tp - 1][i], i >= nw.se ? st[tp - 1][i - nw.se] + nw.fi : 0ll);
    }
    int mid = l + r >> 1;
    if(l == r){
        if(op[l] == 3){
            ll fac = 1ll; 
            rep(m, 1, k) 
                (ans[l] += st[tp][m] * fac % mod) %= mod, (fac *= p) %= mod;
        }
        goto bre;
    }
    qry(ls, l, mid); qry(rs, mid + 1, r);
    bre:;
    while(tp != tp0) --tp;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    cin >> n >> k;
    rep(i, 1, n) cin >> a[i].fi >> a[i].se;
    cin >> q;
    rep(i, 1, n) L[i] = 1, R[i] = q;
    rep(i, 1, q){
        cin >> op[i];
        if(op[i] == 1){
            ++n; cin >> a[n].fi >> a[n].se;
            L[n] = i, R[n] = q;
        }
        if(op[i] == 2){
            int x; cin >> x; R[x] = i;
        }
    }
    rep(i, 1, n) updtr(1, 1, q, L[i], R[i], a[i]);
    qry(1, 1, q);
    rep(i, 1, q) if(op[i] == 3) cout << ans[i] << '\n';
    return 0;
}