自动搬运

查看原文

来自洛谷，原作者为

	lsj2009 关关雎鸠，在河之洲

搬运于2025-08-24 23:09:26，当前版本为作者最后更新于2025-01-27 23:36:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Preface

赛后 20min 调出，，，

Description

定义 $f(a_{1\sim m},b_{1\sim m-1})$ 的值为：

• 对于所有满足如下不等式组的 非负整数 序列 $x_{1\sim n-1}$：$$\begin{cases} x_1 \ge a_1\\ x_1+x_2 \ge a_2\\ \cdots\\ x_{n-2}+x_{n-1}\ge a_{n-1}\\ x_{n-1}\ge a_n \end{cases} $$中 $\sum\limits_{i=1}^{n-1} b_ix_i$ 的最小值。

给定 $a_{1\sim n}$ 和 $b_{1\sim n-1}$，对于任意 $2\le i\le n$ 求出 $f(a_{1\sim i},b_{1\sim i-1})$ 的值。

$1\le n\le 5\times 10^5$，$0\le a_i\le 10^6$。

Solution

记 $V=\max{a_i}$。

考虑一个暴力是从左往右 dp，记 $f_{i,j}$ 表示 $x_{1\sim i-1}$ 的取值已经确定、前 $i-1$ 个不等式的限制已经满足且 $x_{i-1}=j$ 的 $\sum\limits_{j<i} b_jx_j$ 的最小值。

则 $f(a_{1\sim i},b_{1\sim i-1})$ 的值就是 $\min\limits_{j\ge a_i} f_{i,j}$。

简单粗暴地可以得到转移方程：

$$f_{i,j}\gets \left(\min\limits_{k\ge a_{i-1}-j} f_{i-1,k}\right)+j\cdot b_{i-1} $$

可以做到 $\mathcal{O}(nV^2)$ 或 $\mathcal{O}(nV)$。

考虑优化，然后就一拍脑袋说：我猜他是凸的！看看能不能上个 slope trick！

当然有点 corner case：$i\le 2$ 时有些 $f_{i,j}$ 是不合法的，也就是更严谨的是：

• 我们断言：当 $i\ge 3$ 时 $f_{i,*}$ 是下凸的。

套路地考虑 归纳证明：

• 当 $i=3$ 时，不妨对初始的 corner case 暴力讨论一下：
  • 当 $i=1$ 时只有 $f_{1,0}=0$，其余值均可以视作 $\infty$。
  • 当 $i=2$ 时那就是 $j\ge a_1$ 部分是一条从 $(a_1,a_1b_1)$ 开始斜率为 $b_1$ 的射线。其余部分为 $\infty$。
  • 当 $i=3$ 时：
    • 若 $a_2\le a_1$ 则全局范围内为一条从 $(0,a_1b_1)$ 开始斜率为 $b_2$ 的射线。
    • 若 $a_2>a_1$ 则全局范围内为一条 $(0,a_2b_1)-(a_2-a_1,a_1b_1+(a_2-a_1)b_2)$ 斜率为 $b_2-b_1$ 的线段和一条从 $(a_2-a_1,a_1b_1+(a_2-a_1)b_2)$ 开始的斜率为 $b_2$ 的射线。
  • 则当 $i=3$ 时 $f$ 已在 全局范围 内构成了一个 下凸壳。
• 当 $i>3$ 时且我们已经说明 $f_{i-1,*}$ 是下凸的：
  • 找到 $f_{i-1,*}$ 中 最小值的（第一个）取值点 $p$，则考察 $f_{i-1,*}$ 的差分序列 $\mathrm{d}f_{i-1,j}=f_{i-1,j}-f_{i-1,j-1}$ 有：
    • 对于任意 $1\le k\le p$ 有 $\mathrm{d}f_{i-1,k}<0$。
    • 对于任意 $k> p$ 有 $\mathrm{d}f_{i-1,k}\ge 0$。
  • 若 $p\ge a_{i-1}$，则此时 全局斜率变为零，随后 全局斜率增加 $b_{i-1}$。
    • 则此时退化为一条射线，显然仍然为凸的。
  • 若 $p<a_{i-1}$，则此时我们 截取出凸壳在 $[p,a_{i-1}]$ 的部分，将其 翻转（对应到差分序列上为 左开右闭区间翻转再取反），然后 放置在最前面，其余部分斜率推平成 $0$，随后 全局斜率增加 $b_{i-1}$。
    • 全局增加斜率并不影响凸性；考察做此操作之前的凸性：由于对于任意 $k> p$ 有 $\mathrm{d}f_{i-1,k}\ge 0$ 且递增，则 翻转并取反 后仍然递增且不大于 $0$，再接上剩余为 $0$ 的部分仍然符合条件。

对于 $i\le 3$ 的我们可以直接 $\mathcal{O}(V)$ 暴力做；对于 $i>3$ 的部分，根据上面的证明发现我们要支持：

1. 区间翻转。
2. 区间位移（即把三个区间 $x,y,z$ 的顺序变为 $y,x,z$）。
3. 区间取反（即把区间中所有值为 $x$ 的数变为 $-x$）。
4. 区间推平为 $0$。
5. 全局加。

使用 FHQ-Treap 容易维护。具体实现上：

• 注意到 $1,3$ 操作其实操作的区间一致，所以只需要打一个 tag。所以最终需要三个 tag。
• 然后还需要额外 手动维护 $f_{i,0}$ 的值。

视实现最终复杂度是 $\mathcal{O}(n\log{V}+V)$ 或者 $\mathcal{O}(V\log{V})$。

可以参考代码，5.4kb，倒也不算长。

Code

#include<bits/stdc++.h>
#define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
mt19937 rd(time(0));
struct FHQ_Treap {
    static const int N=1e6+5;
    struct node {
        int lson,rson,siz,val,sum,x,tag1,tag2,tag3;
        node() {
            lson=rson=siz=val=sum=tag1=tag2=tag3=0;
        }
        node(int a,int b,int c,int d,int e,int f,int g,int h,int i) {
            lson=a; rson=b;
            siz=c;
            val=d; sum=e;
            x=f;
            tag1=g; tag2=h; tag3=i;
        }
    }; node tree[N];
    #define ls(k) tree[k].lson
    #define rs(k) tree[k].rson
    void push_up(int k) {
        tree[k].siz=tree[ls(k)].siz+tree[rs(k)].siz+1;
        tree[k].sum=tree[ls(k)].sum+tree[rs(k)].sum+tree[k].val;
    }
    int p;
    int new_node(int val) {
        tree[++p]=node(0,0,1,val,val,(int)rd(),0,0,0);
        return p;
    }
    void upd(int k,int t1,int t2,int t3) {
        if(!k)
            return;
        if(t3) {
            tree[k].val=tree[k].sum=0;
            tree[k].tag1=tree[k].tag2=0;
            tree[k].tag3=1;
        }
        if(t1) {
            swap(ls(k),rs(k));
            tree[k].tag1^=1;
            tree[k].val=-tree[k].val;
            tree[k].sum=-tree[k].sum;         
            tree[k].tag2=-tree[k].tag2;   
        }
        tree[k].val+=t2;
        tree[k].sum+=t2*tree[k].siz;
        tree[k].tag2+=t2;
    }
    void push_down(int k) {
        int &t1=tree[k].tag1,&t2=tree[k].tag2,&t3=tree[k].tag3;
        if(t1||t2||t3) {
            upd(ls(k),t1,t2,t3);
            upd(rs(k),t1,t2,t3);
            t1=t2=t3=0;  
        }
    }
    int merge(int u,int v) {
        if(!u||!v)
            return u|v;
        if(tree[u].x<tree[v].x) {
            push_down(u);
            rs(u)=merge(rs(u),v);
            push_up(u);
            return u;
        } else {
            push_down(v);
            ls(v)=merge(u,ls(v));
            push_up(v);
            return v;
        }
    }
    void split(int k,int val,int &u,int &v) {
        if(!k) {
            u=v=0;
            return;
        }
        push_down(k);
        if(tree[k].val<val)
            u=k,split(rs(k),val,rs(k),v);
        else
            v=k,split(ls(k),val,u,ls(k));
        push_up(k);
    }
    void split_siz(int k,int val,int &u,int &v) {
        if(!k) {
            u=v=0;
            return;
        }
        push_down(k);
        if(tree[ls(k)].siz<val)
            u=k,split_siz(rs(k),val-tree[ls(u)].siz-1,rs(k),v);
        else
            v=k,split_siz(ls(k),val,u,ls(k));
        push_up(k);
    }
}; FHQ_Treap T;
const int N=5e5+5,M=1e6+5,m=1e6;
int a[N],b[N],f[2][M],suf[M];
int query(int &rt,int p) {
    int u=0,v=0;
    T.split(rt,0,u,v);
    int mnpos=T.tree[u].siz;
    if(mnpos>=p) {
        int val=T.tree[u].sum;
        rt=T.merge(u,v);
        return val;
    } else {
        rt=T.merge(u,v);
        u=v=0;
        T.split_siz(rt,p,u,v);
        int val=T.tree[u].sum;
        rt=T.merge(u,v);
        return val;
    }
}
void solve() {
    int n;
    scanf("%lld",&n);
    rep(i,1,n)
        scanf("%lld",&a[i]);
    rep(i,1,n-1)
        scanf("%lld",&b[i]);
    cl(f,0x3f);
    int p=1;
    f[1][0]=0;
    rep(i,2,3) {
        p^=1;
        rep(j,0,m)
            f[p][j]=INFLL;
        suf[m+1]=INFLL;
        per(j,m,0)
            suf[j]=min(suf[j+1],f[p^1][j]);
        rep(k,0,m) {
            f[p][k]=INFLL;
            chkmin(f[p][k],suf[max(a[i-1]-k,0ll)]+b[i-1]*k);
        }
        int mn=INFLL;
        rep(j,a[i],m)
            chkmin(mn,f[p][j]);
        printf("%lld\n",mn);
    }
    int x=f[p][0],rt=0;
    rep(i,1,m)
        rt=T.merge(rt,T.new_node(f[p][i]-f[p][i-1]));
    rep(i,4,n) {
        int u=0,v=0;
        T.split(rt,0,u,v);
        int mnpos=T.tree[u].siz;
        if(mnpos<a[i-1]) {
            rt=T.merge(u,v);
            x+=query(rt,a[i-1]);
            int w=0;
            u=v=0;
            T.split_siz(rt,mnpos,u,v);
            int t=v; v=0;
            T.split_siz(t,a[i-1]-mnpos,v,w);
            T.upd(v,1,0,0);
            T.upd(u,0,0,1);
            T.upd(w,0,0,1);
            rt=T.merge(v,T.merge(u,w));
        } else {
            x+=T.tree[u].sum;
            rt=T.merge(u,v);
            T.upd(rt,0,0,1);
        }
        T.upd(rt,0,b[i-1],0);
        printf("%lld\n",x+query(rt,a[i]));
    }
}
bool M2;
// g++ C.cpp -std=c++14 -Wall -O2 -o C
signed main() {
    // file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}