Description
物品集合 (S) 初始为空，按时间递增顺序依次给出 (q) 次操作，操作如下：
-
1 v w e：表示在 (S) 中加入一个体积为 (v) 价值为 (w) 的物品，第 (e) 次操作结束之后移除该物品。 -
2 v：表示询问。你需要回答：- 当前 (S) 是否存在一个子集使得子集中物品体积和为 (v)。
- 当前 (S) 的所有物品体积和为 (v) 的子集中，价值和最大是多少（空集的价值和为 0）。
本题强制在线。
数据范围：(1 leq q leq 15000)，(1 leq v_i leq 15000)，(0 leq w_i leq 15000)。
Solution
如果没有强制在线的话，可以考虑线段树分治，大家应该都会。
对时间轴建一棵线段树。
就是对于每个插入操作，将物品信息挂在线段树上覆盖插入区间的 (mathcal{O}(log q)) 个节点上的 vector 里。
然后遍历整棵树，若当前到达了某个点，就对该点的 vector 上挂着的所有物品跑一遍 (0/1) 背包。然后递归左右儿子。若当前到达了叶节点，是询问的话就直接回答询问即可。回溯时要撤销物品影响。
时间复杂度 (mathcal{O}(qv log q))，说实话我也不知道这个复杂度是怎么跑过去的。
值得注意的是，如果直接开栈储存 dp 数组的修改信息时，空间复杂度会达到 (mathcal{O}(qv log q))。
事实上，我们可以多开一维，记录 dp 数组所处理的节点的深度信息。
例如：f[dep][] 就表示处理到第 ( ext{dep}) 层的某一个节点时，有关该节点的 dp 数组。
在跑 (0/1) 背包的时候，就直接在 f[dep][] 上进行 dp。
在往左右儿子递归的时候，用 (mathcal{O}(v)) 的时间将 f[dep][] 的信息继承给 f[dep + 1][]。
可以归纳证明该做法的正确性，这里留给读者。
这样做，空间复杂度就降到了 (mathcal{O}(v log q))。
如果一定要强制在线的话，还是可以考虑线段树分治。
注意到本题有一个特殊条件：给出物品时同时给出了移除时间。
并且在线段树上遍历的过程，时间是从左到右 (1 o q) 的顺序进行访问的。
这意味这我们可以在没有读入 (q) 个操作时，直接开始遍历过程。
当到达了叶节点时，将操作读进来。如果是插入操作，则将物品信息挂在线段树上覆盖该插入区间的 (mathcal{O}(log q)) 个节点上的 vector 里，显然这样插入，这些被操作的节点一定不会出现曾经被遍历过的节点，也就不影响到曾经的操作了。如果是询问操作，则直接回答询问即可，记得更新 ( ext{lastans})。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
inline int read() {
int x = 0, f = 1; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
return x * f;
}
const int N = 100100;
const int INF = 1e9;
int Q, m, T;
int lastans;
vector< pair<int, int> > art[N * 4];
void insert(int p, int l, int r, int s, int e, pair<int, int> x) {
if (s <= l && r <= e) {
art[p].push_back(x);
return;
}
int mid = (l + r) >> 1;
if (s <= mid)
insert(p * 2, l, mid, s, e, x);
if (mid < e)
insert(p * 2 + 1, mid + 1, r, s, e, x);
}
int f[20][N];
void solve(int p, int l, int r, int dep) {
for (int j = 0; j < (int)art[p].size(); j ++) {
pair<int, int> x = art[p][j];
int w = x.first, v = x.second;
for (int i = m; i >= w; i --)
f[dep][i] = max(f[dep][i], f[dep][i - w] + v);
}
if (l == r) {
int opt = read();
int d = lastans * T;
switch (opt) {
case 1: {
int w = read() - d, v = read() - d, e = read() - d;
insert(1, 1, Q, l + 1, e, make_pair(w, v));
break;
}
case 2: {
int v = read() - d;
int X, Y;
if (f[dep][v] > -INF) X = 1, Y = f[dep][v];
else X = Y = 0;
printf("%d %d
", X, Y);
lastans = X ^ Y;
break;
}
}
} else {
int mid = (l + r) >> 1;
for (int i = 0; i <= m; i ++) f[dep + 1][i] = f[dep][i];
solve(p * 2, l, mid, dep + 1);
for (int i = 0; i <= m; i ++) f[dep + 1][i] = f[dep][i];
solve(p * 2 + 1, mid + 1, r, dep + 1);
}
}
int main() {
Q = read(), m = read(), T = read();
f[0][0] = 0;
for (int i = 1; i <= m; i ++)
f[0][i] = -INF * 2;
solve(1, 1, Q, 0);
return 0;
}