自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:30:32，当前版本为作者最后更新于2021-03-23 20:57:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题使用了一个非常简单的 $\text{trick}$ ，但我相信大部分人都能想得到的（）

题解

一眼扫过该题，你会发现它是个背包板子。先不考虑其他问题，让我们想想朴素的背包做法怎么做。

如果你接触过对顶堆一类的简单科技，你会发现这题相当于将两个背包问题拼接在了一起。你通过聪明才智实现了一个背包类，结构就像是一个堆栈。它支持在顶部插入一种物品，弹出顶部的那种物品，以及快速查询，一个空间为 $v_0$ 的背包能装下的最大价值是多少。简要的实现办法如下：

• 用 $dp_{i,j}$ 表示前 $i$ 个物品，使用不超过 $j$ 的空间可以获得的最大价值。

• 现在加入了一个物品 $(v_i,w_i,t_i)$ ,表示它的体积为 $v_i$ ，价值为 $w_i$ ，类型为 $t_i$ （只有一个，还是有无穷个）。那么转移方程如下：

$$dp_{u,i}=\max\{dp_{u-1,i},dp_{u,i},dp_{u,i-v_i}+w_i\} $$

它的枚举顺序与 $t_i$ 相关。其中， $u$ 表示当前这个物品序列中有多少个物品。

• 删除一个物品就更简单了，你只需要 $u\gets u-1$ 就行了。

回到正题，你现在实现了这样的背包类，然后实例化了两个，不妨称为 $Bag_1,Bag_2$ 。考虑如何完成题目中要求的五种操作。使用类似对顶堆的结构，两个背包的顶端相对。

• 机械臂向右移动。你只要弹出 $Bag_2$ 顶端的物品，然后插入到 $Bag_1$ 顶端就行了。

• 机械臂向左移动。你只要弹出 $Bag_1$ 顶端的物品，然后插入到 $Bag_2$ 顶端就行了。

• 插入一个物品。这一部分也很简单，你直接向 $Bag_2$ 顶部插入一个物品就行了。

• 删除一个物品。与插入物品类似，改为移除 $Bag_2$ 顶部的物品。

• 修改一个物品。比较简单的做法就是直接弹出 $Bag_2$ 顶部，然后再插入一个物品。

你兴致勃勃地实现了所有操作，然后你发现空间是 $\mathcal O(vq)$ 的。于是很幸运地，你 $\text{MLE}$ 了。下面考虑如何优化这个 $Bag$ 类。

---

如果你接触过简单背包问题，那么你应该知道滚动数组优化。可惜的是，这题因为需要支持弹出操作，而滚动数组会丢失掉很多信息，所以朴素的滚动数组是会出锅的。但这不妨是一个很好的启发。

根据某些奇妙的知识（比如学过\sout\text{ Splay}），你就能自然想到把可能访问到的东西放在旁边，用来加速它的访问速度。这题也是如此。

由于操作 $1,2$ 的存在，于是每次操作的位置都是相邻的。考虑记录 $u\in[l,r]$ 时的所有 $dp$ 信息，那么当 $u$ 在这个范围内游走时就可以直接取出对应的 $dp$ 数组了。我们不能无限制开大 $r-l$ 的大小，于是不妨设 $s=r-l$ ，其中 $s$ 是常数。这部分空间复杂度是 $\mathcal O(vs)$ 的。下面考虑 $u$ 跃出这个范围应该如何处理。

背包问题有个非常好的性质，当你知道了 $dp_{u,x}(x\in[0,v])$ ，以及它后面一些物品的属性（大小、价值），你就能快速生成 $dp_{u+1,x},dp_{u+2,x}\cdots$ 。不妨记录 $u\equiv 0\pmod{s'}$ 时的 $dp_{u,x}$ 作为关键点，其中 $s'$ 是常数。当 $u$ 跨出 $[l,r]$ 时就对它进行调整（比如， $u<l$ 时就 $l\gets l-s',r\gets r-s'$ ），然后花费 $\mathcal O(vs)$ 的时间重新生成这一部分的 $dp$ 数组。下面考虑确定这些常数具体的值。

初始时，显然 $l=0,r=s$ 。我们希望每次更新 $l,r$ ，都使得 $u$ 在 $l,r$ 的中点，这样子到下一次更新需要更新 $u$ 的次数最少。于是令 $s'=\frac{1}{2}s$ 。每次更新 $l,r$ ，时间复杂度是 $\mathcal O(vs)$ 。最坏情况下要更新 $\frac{q}{s'}$ 次，于是时间复杂度是 $\mathcal O(vq)$ ，这是没有问题的。关键点的数目是 $\frac{q}{s'}$ ，每个关键点都要维护 $\mathcal O(v)$ 的空间，这部分空间是 $\mathcal O(v\cdot \frac{q}{s'})$ 。同时维护 $[l,r]$ 也要花费 $\mathcal O(vs)$ ，所以总共花费的空间复杂度是 $\mathcal O(v\cdot(\frac{q}{s'}+s))$ ，取 $s=\sqrt{\frac{q}{2}}$ 可以得到最小的空间复杂度。

总时间复杂度 $\mathcal O(vq)$ ，空间复杂度 $\mathcal O(v\sqrt q)$ ，可以通过本题。

参考代码

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