ABC275Ex Monster 题解
Un1quAIoid
·
·
题解
传送门： 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 所需的最小代价。
--------------------
看到这题第一反应是：这不 [[APIO2016] 烟火表演](https://www.luogu.com.cn/problem/P3642) 吗？实际两题在思路和做法上确实非常相似。
首先注意到代价是一个区间极值的形式，而且在代价不变的时候，修改区间肯定是越大越好。不难想到根据 $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)$。
代码：
```cpp
#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;
}
```