困难题。

先考虑假如 $a$ 是确定的我们怎么做。我们先把 $|a_i - b_i|$ 写成 $\max_{-1 \le c_i \le 1} c_i(a_i - b_i)$ 的形式，所以 $f(a) = \min \limits_{b} \max \limits_{-1 \le c_i \le 1} \sum \limits_i c_i(a_i-b_i)$。然后我们就可以把 $\min$ 和 $\max$ 交换一下，变成 $c$ 固定什么时候 $\min \limits_{b} \sum \limits_i c_i(a_i - b_i)$ 是有限的。接下来我们考虑将 $b_i$ 写成 $b_1 + d_1 + \cdots + d_{i-1}$ 的形式，所以我们可以把 $f(a)$ 写成 $\sum \limits_i c_i a_i - b_1 \sum \limits_i c_i - \sum \limits^{m-1}_{j=1} d_j \sum \limits^m_{i=j+1} c_i$。这个时候我们发现如果 $\sum \limits_i c_i \neq 0$，那么我们可以把 $b_1$ 往一个方向无限拉，然后这个式子就变成了 $-\infty$。同理对于 $\sum \limits^m_{i=j+1} c_i$ 如果这个东西是 $> 0$ 的，那么肯定不行，因为我们可以把 $d_j$ 往一个方向无限拉，然后这个式子也变成了 $-\infty$。那么我们就得到了 $\sum \limits^m_{i=j+1} c_i \le 0$。所以这个时候我们肯定是令 $b_i = 0$ 这样子最优秀。那么我们最终就得出了 $f(a) = \max \limits_{|c_i| \le 1,\\ \sum_i c_i = 0,\\ \sum^i_{j=1} c_i \ge 0} c_i a_i$。也就是一个类似于括号匹配东西。

然后假设此时我们需要假如一个 $i = p_k$，那么他有以下几个选法：

• 不选他，直接令 $c_i = 0$。
• 选他作为左端点，即令 $c_i = 1$，然后找到一个 $c_j \in {0,1}$，让 $c_j \gets c_j - 1$，收益为 $a_i - a_j$。这里由于需要满足 $\sum^i_{j=1} c_i \ge 0$，所以这个 $j$ 需要在 $i$ 左侧离 $i$ 最近 $0$ 后面。
• 选他作为右端点，即令 $c_i = -1$，然后找到一个 $c_j \in {-1,0}$，让 $c_j \gets c_j + 1$，收益为 $a_j - a_i$。这里由于需要满足 $\sum^i_{j=1} c_i \ge 0$，所以这个 $j$ 需要在 $i$ 右侧离 $i$ 最近的 $0$ 前面。

所以我们需要用线段树支持一下操作和询问：

• 区间加，线段树上二分。
• 单点修改，维护区间最值。

这个我们直接开 $4$ 棵线段树分别维护区间和，$-1/0/1$ 的位置即可。