题解 P3991 【[BJOI2017]喷式水战改】

· · 题解

这题其实想清楚还是挺好写的，代码连100行都不到

首先考虑如果没有插入操作，就给定一个序列怎么做，那就是一个非常简单的一维（二维？）dp，我们用f_{i,j}表示第i个点当做第j个区间来使用（为了方便，我们把四个区间标记成0,1,2,3），其中0和3的价格是完全相同的。那么转移就是

f_{i,j}=\max\{f_{i-1,k}+val\},k\leq j

然后我们会到原题里面，有插入操作，显然想到平衡树

那么我们一个类似这样的dp搬到平衡树上就好了

我们用f[u] _{i,j} 表示平衡树上编号为u的节点当他代表的是[i,j]这两个工作模式的时候的最大方法(两段可以不选)

那么我们就只需要改一下update的写法就可以，转移就是

f[u]_{i,k}=\max\{f[lc]_{i,j}+val[u]_j+f[rc]_{j,k}\}

貌似没有ClCN姐姐的那么麻烦？（

但是这题还有一个恶心的地方就是有n次操作，每次插入x个数，最差的时候会插入10^{14}个数，炸飞了

怎么呢？我们可以用ODT的思想把连续一段相同的合并到一个点上

每次插入的时候判断一下，如果插到了一个点的中间，就需要把这个点拆成两个

那么可以发现每次插入的时候最多多三个点，如果开空间回收只用开3倍空间就可以，不开4倍也够了，当然我为了保险开了5倍

那么我们最后的复杂度就是O(64n\log n)，时限三秒可以通过（因为64还比较大所以单独写出来了）

当然因为需要拆点还有一点点小细节

比如说我们怎么确定我们要插入的这个点位于哪个序列里面呢？我们split按什么split呢？

可以按照平衡树上的节点数siz进行split，也可以按照实际上的燃料数sum进行split，当然可以两次分别split一下，但是其实是没有必要的

我们应该选择按照第一种方法，平衡树上的节点数进行split

为什么呢？比如说我们把p所在的点按照sum拆出来了，那么从哪里把这个点劈成两半呢？我们不知道

但是如果按照siz拆出来，我们是可以利用siz表示出sum的，所以我们应该按照siz进行split

那么我们可以根据sum上的排名（已知）去找siz上的排名，然后根据排名split

然后特判插入的位置在末尾的情况，再还原就可以了

当然，开了longlong之后，记得输出%lld

本来写了个没啥用的空间回收，后来为了把代码卡进100行给删了

为啥删掉空间回收还变慢了500ms呢

最后卡到95行的代码：

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=5e5+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n;
int son[N][2],treap[N],val[N][4],len[N],siz[N];
ll sum[N],f[N][4][4];
ll ans;
int rt,tot;
int bin[N],top;

void update(int x){
    memset(f[x],0,sizeof(f[x]));
    Rep(i,0,3)
        Rep(j,i,3)
            Rep(k,j,3)
                f[x][i][k]=max(f[x][i][k],f[son[x][0]][i][j]+1ll*val[x][j]*len[x]+f[son[x][1]][j][k]);
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+len[x];
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}

void split(int o,int &u,int &v,int k){
    if(!o){u=v=0;return;}
    int rank=siz[son[o][0]]+1;
    if(rank<=k)split(son[u=o][1],son[o][1],v,k-rank);
    else split(son[v=o][0],u,son[o][0],k);
    update(o);
}   

int merge(int u,int v){
    if(!u||!v)return u|v;
    int rt;
    if(treap[u]<treap[v])son[rt=u][1]=merge(son[u][1],v);
    else son[rt=v][0]=merge(u,son[v][0]);
    return update(rt),rt;
}

int rnk(ll k){
    int u=rt,res=0;
    while(u){
        if(sum[son[u][0]]>=k)u=son[u][0];
        else if(sum[son[u][0]]+len[u]>=k)return res+siz[son[u][0]]+1;
        else k-=sum[son[u][0]]+len[u],res+=siz[son[u][0]]+1,u=son[u][1];
    }
    return res;
}

int main()
{
    srand(19260817);
    read(n);
    Rep(i,1,n){
        ll p,x;
        int u=++tot;
        read(p),read(val[u][0]),read(val[u][1]),read(val[u][2]),read(x),val[u][3]=val[u][0];
        int rank=rnk(p);
        int lef,mid,rht;
        split(rt,lef,rht,rank);
        split(lef,lef,mid,rank-1);
        siz[u]=1,sum[u]=len[u]=x;
        son[u][0]=son[u][1]=0;
        treap[u]=rand();
        update(u);
        if(sum[lef]+len[mid]==p)rt=merge(merge(lef,mid),merge(u,rht));
        else{
            int l=++tot,r=++tot;
            Rep(i,0,3)val[l][i]=val[r][i]=val[mid][i];
            siz[l]=siz[r]=mid;
            son[l][0]=son[r][0]=son[l][1]=son[r][1]=0;
            sum[l]=len[l]=p-sum[lef];
            sum[r]=len[r]=sum[lef]+sum[mid]-p;
            treap[l]=rand(),treap[r]=rand();
            update(l),update(r);
            rt=merge(merge(lef,merge(l,u)),merge(r,rht));
        }
        printf("%lld\n",f[rt][0][3]-ans);
        ans=f[rt][0][3];
    }
    return 0;
}