题目描述

有若干个物品,每个物品有两个属性:质量 $w$ 和价值 $v$。现在有三种操作:

  1. 加入一个质量为 $w$,价值为 $v$ 的物品。
  2. 删除 (之前已存在的) 某个物品。
  3. 询问当 $i = 1, 2, \cdots, k$ 时,一个容量 (即最大载重量) 为 $i$ 的背包所能装下的物品的总价值的最大值。(其中 $k$ 为常数)

对于每个操作 3,请输出对应的答案。

输入格式

第一行包含两个正整数 $n, k$ ($n \leq 5000, k \leq 1000$),$n$ 表示初始的物品总数,$k$ 的意义见题目描述。

接下来的 $n$ 行,每行包含两个正整数 $v_i, w_i$ ($v_i \leq 10^6, w_i \leq 1000$),表示第 $i$ 个物品的价值和质量。

紧接着一行包含一个正整数 $q$ ($q \leq 30000$),表示操作的个数。

接下来的 $q$ 行,每行描述一个操作,以如下形式给出:

  1. 1 v w($v \leq 10^6, w \leq 1000$) 表示加入了一个价值为 $v$,质量为 $w$ 的物品,该物品的编号为未出现过的最小编号

  2. 2 x表示删除编号为 $x$ 的物品,保证编号为 $x$ 的物品存在且未被删除。
  3. 3表示询问当 $i = 1, 2, \cdots, k$ 时的背包询问。

保证操作 3 的个数不超过 $10000$。

输出格式

考虑到输出数的个数太多,我们将操作 3 以一种特殊的方式输出。

对于每个操作 3,记 $s(m)$ 表示当 $i = m$ 时的背包询问的结果,则输出一行一个整数 $$ \left( \sum_{i=1}^k s(i) \cdot p^{i-1} \right) \bmod q $$ 其中 $p = 10^7 + 19, q = 10^9 + 7$。

题解

首先能注意到如果在线做 (这个动态背包问题),那么是非常难实现删元素的,那么这道题应该是离线处理。

离线处理有这么几种算法:首先莫队显然是没有希望的,陈丹琦分治嘛,可以搞搞。不过根据这道题的经验,继续尝试时间戳线段树

完全类似地,对于每一个物品,我们求出它的存在时间 (这显然是一个区间),然后将它加入线段树,它至多被分散成 $O(\log n)$ 个节点。

然后考虑询问,由于总时间 (即操作 3 的个数) 不超过 $10000$,因此考虑枚举每个叶节点,只需对它到根的路径上的所有节点中的物品,做一遍背包 DP 即可。

这样的时间复杂度是 $O(q^2)$ 的,不过可以看出,仍旧有很多物品经历了重复计算,因此还可以进一步优化。

考虑最后 solve() 时对整棵线段树 dfs,每 dfs 到一个点时,在该节点保存一下 DP 值。然后下一次 DP 时直接加入一个新的物品即可。这样的空间是 $O(k \log q)$ 的,不会爆掉。

最后输出其实就是个多项式,暴力和秦九韶算法都可以。总时间复杂度 $O(qk \log q)$。

代码

#include <bits/stdc++.h>
#define N 34147
#define K 1034
#define segc int M = (L + R - 1) >> 1, lc = id << 1, rc = lc | 1
using namespace std;

typedef vector <int> vec;
typedef long long ll;
const ll base = 10000019, mod = 1000000007;

struct exhibit{
	int w, c, l, r;
	exhibit (int w0 = 0, int c0 = 0, int l0 = 1, int r0 = -1): w(w0), c(c0), l(l0), r(r0) {}
	exhibit * read(int l0 = 1) {scanf("%d%d", &c, &w); l = l0; return this;}
}e[N];

int n, q, t = 1, W;
int op, i;
ll __empty__[K];
vec st[N << 2];

inline void up(ll &x, const ll y) {x < y ? x = y : 0;}

void add(int id, int L, int R, int ql, int qr, int v){
	if(ql <= L && R <= qr) {st[id].push_back(v); return;}
	segc;
	if(ql <= M) add(lc, L, M, ql, min(qr, M), v);
	if(qr > M) add(rc, M + 1, R, max(ql, M + 1), qr, v);
}

void solve(int id, int L, int R, ll *f){
	int i, j, n = (int)st[id].size();
	ll g[K]; memcpy(g, f, sizeof g);
	for(i = 0; i < n; ++i){
		exhibit &t = e[st[id][i]];
		for(j = W; j >= t.w; --j)
			up(g[j], g[j - t.w] + t.c);
	}
	if(L == R){
		ll res = 0;
		for(i = W; i; --i) res = (res * base + g[i]) % mod;
		printf("%d\n", (int)res); return;
	}
	segc; solve(lc, L, M, g); solve(rc, M + 1, R, g);
}

int main(){
	scanf("%d%d", &n, &W);
	for(i = 1; i <= n; ++i) e[i].read();
	for(scanf("%d", &q); q; --q)
		switch(scanf("%d", &op), op){
			case 1: e[++n].read(t); break;
			case 2: scanf("%d", &i); e[i].r = t - 1; break;
			case 3: ++t; break;
		}
	--t;
	for(i = 1; i <= n; ++i)
		if(e[i].l <= (~e[i].r ? e[i].r : (e[i].r = t)))
			add(1, 1, t, e[i].l, e[i].r, i);
	solve(1, 1, t, __empty__);
	return 0;
}

坑1:注意物品的总数是 $O(q)$ 的而不是 $O(n)$ 的,因此线段树别开小了。