题解 【SR2.5-T3】【未来水妖集市】

· · 题解

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

题解

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

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

回到正题，你现在实现了这样的背包类，然后实例化了两个，不妨称为 Bag_1,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;
}