本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-03 17:40:54

传送门： ABC275Ex

题目大意：

给定 $n$ 以及两个长度为 $n$ 的正整数序列 $A_i,B_i$，你可以执行下述操作任意次：

• 选定任意整数 $l,r$，满足 $1 \le l \le r \le n$。
• 花费 $max_{i=l}^{r} \{B_i\}$ 的代价，将 $A_l,A_{l+1}, \dots A_r$ 中每个都减去 $1$。

请求出使得 $A_i$ 中元素全部 $\le 0$ 所需的最小代价。

$1 \le n \le 10^5, 1 \le A_i,B_i \le 10^9$。

看到这题第一反应是：这不 [APIO2016] 烟火表演 吗？实际两题在思路和做法上确实非常相似。

首先注意到代价是一个区间极值的形式，而且在代价不变的时候，修改区间肯定是越大越好。不难想到根据 $B$ 建立笛卡尔树，一次操作就是选择一个节点 $i$，花费 $B_i$ 的代价使得 $x$ 子树内所有点对应的 $A$ 减 $1$。

其次，我们只需要关心子树内当前 $A$ 的最大值，可以设计 dp 状态 $f_{i,j}$ 表示当前子树 $i$ 内 $A$ 的最大值 $\le j$ 时所需的最小代价，设点 $i$ 的左右儿子分别为 $x,y$，不难得到转移方程：

$$ \begin{aligned} f_{i,j} &= \min_{k = \max(j,A_i)}^{+\infty} \{f_{x,k}+f_{y,k}+(k-j)B_i \}\ &= -B_ij + \min_{k = \max(j,A_i)}^{+\infty} \{f_{x,k}+f_{y,k}+B_ik \} \end{aligned} $$

这样做是 $O(nV)$ 的，显然要从值域入手优化。将 $f_{i,j}$ 看作关于 $j$ 的函数，对于这种没有明显特征的转移方程，可以手玩一下小一点的数据，观察 $f_{i,j}$ 的图像，可以看出 $f_{i,j}$ 是一次分段下凸函数（其实题做多了以后，看到这个式子的第一反应就是凸性优化）。

证明可以考虑归纳法，首先空节点的 $f$ 图像就是与横轴重合的直线，满足归纳假设，接下来先考虑 $f_{x,k}+f_{y,k}+B_ik$，显然这是三个一次分段凸函数相加（$B_ik$ 就是一条斜率为 $B_i$ 的直线），结果仍然是一次分段凸函数，图像大致长这样：

观察 $\min_{k= \max(j,A_i)}^{+\infty}$ 对这个函数图像的变换效果，首先找到直线 $x=A_i$ 右侧的最低点（图中为点C），对于最低点左侧的部分，其函数值等于最低点对应的函数值，右侧保持不变，也就是长这样（红色部分）：

当然也可能长这样：

可以看作是将斜率小于 $0$ 以及 $\le A_i$ 的部分全部删掉，并在一开始加入一段斜率为 $0$ 的线段，变换后再加上 $-B_ij$（一条直线），很明显依然是一个一次分段下凸函数。

很明显一次转移最多新加入 $O(1)$ 条线段，所以总段数是 $O(n)$ 的，考虑用数据结构加速维护过程，官方题解使用的是 set+启发式合并，时间复杂度 $O(n \log^2n)$。不过这个东西用可并堆也非常容易维护，具体来说，可以维护图像上拐点的横坐标以及拐点右侧线段与左侧线段斜率之差，按照横坐标大小维护小根堆，两个函数相加就直接把两个堆合并起来，进行 $\min_{k= \max(j,A_i)}^{+\infty}$ 这个变换的时候就直接暴力删点，总共只会删 $O(n)$ 次，总复杂度 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1e5+5;
const int Mod = 998244353;

int n, A[MAXN], B[MAXN];
int l[MAXN], r[MAXN], stk[MAXN], top;
int rt[MAXN], tot;
ll cur[MAXN];

struct node {
    int ls, rs, dis;
    ll x, k;
} H[MAXN * 4];

int merge(int a, int b) {
    if (!a || !b) return a | b;
    if (H[a].x > H[b].x) swap(a, b);
    H[a].rs = merge(H[a].rs, b);
    if (H[H[a].rs].dis > H[H[a].ls].dis) swap(H[a].ls, H[a].rs);
    H[a].dis = H[H[a].rs].dis + 1;
    return a;
}

inline void push(int num, ll x, ll k) {
    H[++tot].x = x;
    H[tot].k = k;
    rt[num] = merge(tot, rt[num]);
}

inline void pop(int num) {
    rt[num] = merge(H[rt[num]].ls, H[rt[num]].rs);
}

void dfs(int x) {
    if (!x) return;
    dfs(l[x]), dfs(r[x]);
    cur[x] = cur[l[x]] + cur[r[x]];
    rt[x] = merge(rt[l[x]], rt[r[x]]);
    push(x, 0, B[x]);
    ll curx = 0, curk = 0;\/\/当前斜率
    while (1) {
        curx = H[rt[x]].x;
        curk += H[rt[x]].k;
        if (curk >= 0 && curx >= A[x]) {
            H[rt[x]].k = curk;
            push(x, 0, 0);
            break;
        }
        pop(x);
        if (curk >= 0 && (!rt[x] || H[rt[x]].x >= A[x])) {
            cur[x] += curk * (A[x] - curx);
            push(x, A[x], curk);
            push(x, 0, 0);
            break;
        }
        cur[x] += curk * (H[rt[x]].x - curx);
    }
    push(x, 0, -B[x]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &B[i]);

    for (int i = 1; i <= n; i++) {
        int lst = 0;
        while (top && B[stk[top]] <= B[i]) {
            r[stk[top]] = lst;
            lst = stk[top--];
        }
        l[i] = lst;
        stk[++top] = i;
    }
    for (int i = 2; i <= top; i++) r[stk[i - 1]] = stk[i];

    dfs(stk[1]);

    printf("%lld", cur[stk[1]]);
    return 0;
}