题解：P11678 [USACO25JAN] Watering the Plants P

· · 题解

更多凸性优化

令 c_i 表示第 i 株植物需要的水量，w_i 表示连接 i,i+1 的水渠的单位代价。

定义 f_i(j) 表示前 i 株植物已经搞定并且给第 i+1 株植物额外贡献了 j 的水量时的最小代价，转移是简单的，枚举第 i-1 个水渠用了 k 的水，于是

f_i(j)=\min_{k+j\ge c_i}\set{f_{i-1}(k)+j\times w_i} \\ =\min_{k\ge \max(0,c_i-j)}f_{i-1}(k)+j\times w_i

使用后缀 \min 优化一下：

g_i(j)=\min_{k\ge j}f_i(k) \\ f_i(j)=g_{i-1}(\max(0,c_i-j))+j\times w_i

我们将 j 分类：

由于 g_{i-1}(0) 在 g_{i-1} 中为最大值，可以发现 f_i 是凸的，由此考虑凸性优化。

还是分开来看：

做完之后，全部推成后缀 \min，后缀 \min 一定是一个平台加上一个单调上升。即：

我们考虑维护点到点斜率，注意，此处的斜率其实相当于 f 的差分。

观察转移式，我们要求的答案是 f_i(0)，可以发现 f_i(0)=g_{i-1}(c_i)，如何求 g_{i-1}(c_i)？注意到我们是知道 f_{i-1}(0) 的，那么可以通过斜率推导一下：

具体的，我们令 s 表示斜率 k<0 的部分的斜率之和，那么通过 f_{i-1}(0)+s 即可算出 g_{i-1}(0)，即图中蓝色平台的高度。我们知道 g_{i-1,0}，那么从前往后加上斜率加到 c_i 就可以推出 g_{i-1,c_i}，这个的理解其实就是差分的前缀和是原数组，即令后面斜率 k>0 的部分到 c_i 的斜率和为 S，那么 g_{i-1}(c_i)=f_{i-1}(0)+s+S，也就是 f_i(0)。于是我们可以通过这种方式不断往后迭代，即可求解出所有的 f_i(0)。

维护斜率可以用平衡树，操作有【区间翻转】、【区间取反（翻转后斜率都取反）】、【覆盖成 0】、【加上 w_i】的操作，可以变成【区间翻转】、【区间乘】、【区间加】，用平衡树维护，并且要在平衡树上二分找到拐点推平，然后要计算前缀和，所以再维护一个前缀和。

然后就可以了，时间复杂度 O(n\log V)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

typedef long long ll;
const int N=500010,M=1000010;
const ll INF=1e18;
int n;
int c[N],w[N];
int mx;

void Min(ll &x,ll y) { x=min(x,y); }

namespace FHQ
{
    mt19937 rnd(time(0));

    ll val[M],sum[M],add[M];
    int pri[M],ch[M][2],sz[M],rev[M],mul[M],idx,root;

    inline int new_node(int v)
    {
        int u=++idx;
        val[u]=sum[u]=v;
        pri[u]=rnd();
        sz[u]=1;
        mul[u]=1;
        return u;
    }

    inline void pushup(int u) 
    {
        sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
        sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u];
    }

    inline void Rev(int u)
    {
        if (!u) return;
        rev[u]^=1;
        swap(ch[u][0],ch[u][1]);
    }

    inline void Mul(int u,int x)
    {
        if (!u) return;
        mul[u]*=x;
        add[u]*=x;

        val[u]*=x;
        sum[u]*=x;
    }

    inline void Add(int u,int d)
    {
        if (!u) return;
        add[u]+=d;

        val[u]+=d;
        sum[u]+=(ll)d*sz[u];
    }

    inline void pushdown(int u)
    {
        if (rev[u])
        {
            Rev(ch[u][0]);
            Rev(ch[u][1]);
            rev[u]=0;
        }
        if (mul[u]!=1)
        {
            Mul(ch[u][0],mul[u]);
            Mul(ch[u][1],mul[u]);
            mul[u]=1;
        }
        if (add[u])
        {
            Add(ch[u][0],add[u]);
            Add(ch[u][1],add[u]);
            add[u]=0;
        }
    }

    void split(int rt,int k,int &rt1,int &rt2)
    {
        if (!rt) 
        {
            rt1=rt2=0;
            return;
        }
        pushdown(rt);
        if (sz[ch[rt][0]]+1<=k) 
        {
            rt1=rt;
            split(ch[rt][1],k-sz[ch[rt][0]]-1,ch[rt][1],rt2);
        }
        else
        {
            rt2=rt;
            split(ch[rt][0],k,rt1,ch[rt][0]);
        }
        pushup(rt);
    }

    int merge(int rt1,int rt2)
    {
        if (!rt1 || !rt2) return rt1^rt2;
        if (pri[rt1]<pri[rt2])
        {
            pushdown(rt1);
            ch[rt1][1]=merge(ch[rt1][1],rt2);
            pushup(rt1);
            return rt1;
        }
        else
        {
            pushdown(rt2);
            ch[rt2][0]=merge(rt1,ch[rt2][0]);
            pushup(rt2);
            return rt2;
        }
    }

    inline void Insert(int v) { root=merge(root,new_node(v)); }

    ll qrys(int u,int k)
    {
        if (!u) return 0;
        pushdown(u);
        if (sz[ch[u][0]]+1<=k) return sum[ch[u][0]]+val[u]+qrys(ch[u][1],k-sz[ch[u][0]]-1);
        else return qrys(ch[u][0],k);
    }

    ll mdf(int u)
    {
        if (!u) return 0;
        pushdown(u);
        if (val[u]<0) 
        {
            ll res=sum[ch[u][0]]+val[u]+mdf(ch[u][1]);
            Mul(ch[u][0],0),val[u]=0;
            pushup(u);
            return res;
        }
        else 
        {
            ll res=mdf(ch[u][0]);
            pushup(u);
            return res;
        }
    }

    void adj(int rt=root)
    {
        pushdown(rt);
        if (ch[rt][0]) adj(ch[rt][0]);
        if (ch[rt][1]) adj(ch[rt][1]);
        pushup(rt);
    }

    void print(int rt=root)
    {
        if (ch[rt][0]) print(ch[rt][0]);
        cout << val[rt] << " ";
        if (ch[rt][1]) print(ch[rt][1]);
    }

    void prt(int rt=root) { adj(rt);print(rt);cout << "\n---\n"; }
}
using namespace FHQ;

ll f0;
ll st;

inline ll calc(int k)
{
    ll res=st+f0+qrys(root,k);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n;
    for (int i=1;i<=n;i++) 
    {
        cin >> c[i];
        mx=max(mx,c[i]);
    }
    for (int i=1;i<n;i++) cin >> w[i];

    for (int i=1;i<=c[1];i++) Insert(0);
    for (int i=c[1]+1;i<=mx;i++) Insert(w[1]);
    f0=(ll)c[1]*w[1];

    for (int i=2;i<=n;i++)
    {
        st=mdf(root);

        f0=calc(c[i]);
        cout << f0 << "\n";

        int x,y;
        split(root,c[i],x,y);
        Rev(x);Mul(x,-1);Mul(y,0);
        root=merge(x,y);
        Add(root,w[i]);
    }

    return 0;
}