题解：CF601E A Museum Robbery

Happy New Year!

Solution

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

发现是背包，~~想到猫树~~。背包是典型的合并复杂度非常高的信息。发现我们能承受的复杂度是加入一个物品的

O(k)

，而非合并两个背包的

O(k^2)

。

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

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

1e4

”的条件了。

时间复杂度

O(nk\log q)

。

Code

CPP

#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;
}

题解：CF601E A Museum Robbery

文章操作

Solution

Code

相关推荐

评论

题解：CF601E A Museum Robbery