Wine Factory

· · 题解

Win Factory

题意已经很简明了，这里不加以阐述，注意到 c_i,z=10^{18}，但是 n \leq 5 \times 10^5，a_i \leq 10^9，也就是说，所有桶里面装的水都不会超出桶容量或者管道容量。

到这里，其实求解策略就很明显了，从第 1 个水桶开始，只要巫师还有法力，就转化成酒，直到水用完或者法力用完，如果还有剩下的水，就流到下一个水桶去，和下一个水桶一起处理。

要是这题没有修改就已经贪心做完了，在有修改的情况下，数学功底比较好的人可以把答案用式子表示出来然后硬推，这里提供一种不同的思考方向。

考虑这样一个问题：假设水足够多，那么答案就是巫师的法力总和，但是在大多时候答案却小于这个值，少的那一部分去哪里了呢？也就是说巫师的法力在什么情况下会浪费掉？

显然，对于水桶 i 如果 a_i 加上前面水桶流过来的水小于 b_i 就会导致法力的浪费，但是前面水桶流过来的水很难表示。发现第一个桶浪费的法力为 b_i-a_i，当这个值为正时，表示浪费的法力；为负时，其绝对值表示盈余的水。

如果对这个值做一遍前缀和是什么呢？令 s_i=\sum_{j=1}^i b_j-a_j，如果这个值在上升，就说明 b_i-a_i>0，即法力的浪费，反之表示水的剩余。那么它和答案的联系是啥呢？请仔细结合下面这幅表示 s_i 变化的图象来理解：

理解完过程后，再来看如何计算浪费值，图中两段粉线相加即为浪费值，显然，它们相加就是最高点的高度，即 \max_{i=1}^n(s_i)。需要注意的是，浪费值不可能为负，也就是说当最大值是负数时，把浪费值当做 0 即可。

有了浪费值，答案就是法力总和减掉浪费值，即 \sum_{i=1}^n b_i-\max_{i=1}^n(s_i)，在修改过程中，前面的 \sum 用一个变量维护，而后面相当于是求全局最大值，由于修改了一个值 i 之后，前缀和 s_i \sim s_n 都会改变，相当于是区间修改，区间查询，用线段树即可维护。

Code：

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

const int maxn=5e5+7;
int n,m,id,x,y,sum;
int a[maxn],b[maxn],s[maxn],dat[maxn<<2],laz[maxn<<2];

void pushdown(int rt){
    if(laz[rt]){
        dat[rt<<1]+=laz[rt];
        dat[rt<<1|1]+=laz[rt];
        laz[rt<<1]+=laz[rt];
        laz[rt<<1|1]+=laz[rt];
        laz[rt]=0;
    }
    return ;
}

void build(int rt,int l,int r){
    if(l==r){
        dat[rt]=s[l];
        return ;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
    dat[rt]=max(dat[rt<<1],dat[rt<<1|1]);
    return ;
}

void update(int rt,int l,int r,int x,int y,int val){
    if(x<=l&&y>=r){
        dat[rt]+=val,laz[rt]+=val;
        return ;
    }
    int mid=l+r>>1;
    pushdown(rt);
    if(x<=mid) update(rt<<1,l,mid,x,y,val);
    if(y>mid) update(rt<<1|1,mid+1,r,x,y,val);
    dat[rt]=max(dat[rt<<1],dat[rt<<1|1]);
    return ;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]),sum+=b[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i]-a[i];
    for(int i=1;i<n;i++) scanf("%*lld");
    build(1,1,n);
    while(m--){
        scanf("%lld%lld%lld%*lld",&id,&x,&y),sum+=y-b[id];
        update(1,1,n,id,n,y-x-(b[id]-a[id]));
        a[id]=x,b[id]=y;
        printf("%lld\n",sum-max(dat[1],0ll));
    }
    return 0;
}