#include<bits/stdc++.h> #define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i) #define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i) using namespace std; typedef long long i64; int qread() { int w = 1, c, ret; while ((c = getchar()) > '9' || c < '0') w = (c == '-' ? -1 : 1); ret = c - '0'; while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0'; return ret * w; } const int MAXN = 2e4 + 3, MAXM = 175 + 3, MAXQ = 3e4 + 3, SI = 4; int q, v, s, o; struct Node { int x, y; bool t; Node(int _x, int _y, bool _t) :x(_x), y(_y), t(_t) {} }; class Bag { public: int t, l, r, X[MAXQ], Y[MAXQ]; bool F[MAXQ]; int W[MAXM][MAXN], M[MAXM][MAXN]; void iit(bool f) { l = 0, r = 2 * s - 1; } void add(Node e) { ++t; int x = X[t] = e.x, y = Y[t] = e.y; bool f = F[t] = e.t; if (t - 1 == r) { //t==r+1 -> t=r-s+1 up(0, s - 1, j) up(0, v, k) W[j][k] = W[j + s][k]; l += s, r += s; } up(0, v, j) W[t - l][j] = W[t - l - 1][j]; if (f) up(x, v, j) W[t - l][j] = max(W[t - l][j], W[t - l][j - x] + y); else dn(v, x, j) W[t - l][j] = max(W[t - l][j], W[t - l][j - x] + y); if (t % s == 0) up(0, v, j) M[t / s][j] = W[t - l][j]; } void ers() { --t; if (t + 1 == l) { l -= s, r -= s; up(0, v, j) W[0][j] = M[l / s][j]; up(1, s - 1, j) { int x = X[l + j], y = Y[l + j]; bool f = F[l + j]; up(0, v, k) W[j][k] = W[j - 1][k]; if (f) up(x, v, k) W[j][k] = max(W[j][k], W[j][k - x] + y); else dn(v, x, k) W[j][k] = max(W[j][k], W[j][k - x] + y); } } } Node bnk() { return Node(X[t], Y[t], F[t]); } int val(int x) { return W[t - l][x]; } }B1, B2; int slv(int x) { int r = 0; up(0, x, i) r = max(r, B1.val(i) + B2.val(x - i)); return r; } int main() { q = qread(), v = qread(), s = 1 + sqrt(q + 1) / 2, B1.iit(1), B2.iit(0); up(1, q, i) { i64 opt = qread() ^ o, ti = qread() ^ o, vi = qread() ^ o, wi = qread() ^ o, xi = qread() ^ o, yi = qread() ^ o; switch (opt) { case 1: B1.add(B2.bnk()), B2.ers(); break; case 2: B2.add(B1.bnk()), B1.ers(); break; case 3: B2.add(Node(vi, wi, ti)); break; case 4: B2.ers(); break; case 5: B2.ers(), B2.add(Node(vi, wi, ti)); } printf("%d\n", o = xi + slv(yi)); } return 0; }动态规划

这是一篇使用了动态规划的代码。其中，Bag类维护了一个线性序列，支持添加元素、删除尾部元素、获取指定位置的元素等操作。同时，Bag类还支持对该线性序列进行动态规划，计算出满足一定条件的最大值。

在这个代码中，我们使用了两个Bag类来维护两个序列，分别表示 $T_1$ 和 $T_2$。下面简要介绍一下这个代码的主要流程：

1. 读入数据

2. 初始化两个Bag类。其中，s 表示 Bag 类维护的线性序列的长度，由于我们需要使用根号分治，所以 s 的取值为 $\sqrt{q+1}/2+1$。

3. 进行循环，对于每一个操作，执行相应的操作。如果是 1 操作，则将 $T_2$ 的尾部元素加入 $T_1$ 中，同时删除 $T_2$ 的尾部元素；如果是 2 操作，则将 $T_1$ 的尾部元素加入 $T_2$ 中，同时删除 $T_1$ 的尾部元素；如果是 3 操作，则将元素 $(v_i,w_i,t_i)$ 加入 $T_2$ 中；如果是 4 操作，则删除 $T_2$ 的尾部元素；如果是 5 操作，则先删除 $T_2$ 的尾部元素，再将元素 $(v_i,w_i,t_i)$ 加入 $T_2$ 中。

4. 对于每一个询问 $(x_i,y_i)$，计算出相应的答案。

下面我们重点来看一下如何计算相应的答案。由于我们需要满足 $v_1+v_2\leq y_i$ 的条件，因此我们可以枚举 $v_1$，然后计算出 $T_1$ 中前 $v_1$ 个元素的最大价值 $val_1$，以及 $T_2$ 中前 $y_i-v_1$ 个元素的最大价值 $val_2$。那么，$val_1+val_2$ 就是满足条件的最大价值。最后，将 $x_i$ 加上这个最大价值，即为相应的答案。