CF1988E Range Minimum Sum
Alex_Wei
·
·
题解
CF1988E Range Minimum Sum
对于不删数的经典问题，一种做法是枚举最小值的位置 p。设 l, r 分别表示 p 左右两侧值小于 a_p 的第一个位置，若不存在则为 0 和 n + 1，则所有左端点在 [l + 1, p]，右端点在 [p, r - 1] 的子区间的最小值为 a_p。
推广到本题，依然枚举最小值的位置 p。考察删去不同位置时最小值为 a_p 的子区间数量 c 的情况。
- 如果删去 p，那么显然 c = 0。
- 如果删去 [l + 1, p - 1] 的某个位置，那么 c = (p - l - 1)(r - p)。
- 如果删去 [p + 1, r - 1] 的某个位置，那么 c = (p - l)(r - p - 1)。
- 如果删去 [1, l - 1]\cup [r + 1, n] 的某个位置，那么 c = (p - l)(r - p)。
- 如果删去 l，设 l_2 为 l 左侧值小于 a_p 的第一个位置，那么 c = (p - l_2 - 1)(r - p)。
- 如果删去 r，设 r_2 为 r 右侧值小于 a_p 的第一个位置，那么 c = (p - l)(r_2 - p - 1)。
$l_2$ 的线性求法：按 $l$ 从小到大为第一关键字，$a$ 从大到小为第二关键字的顺序考虑所有位置，对每个位置，依次往栈内加入上一个位置的 $l$ 到当前位置的 $l - 1$ ，然后弹出所有值大于 $a$ 的位置，则栈顶即为 $l_2$。$r_2$ 同理。[代码](https://codeforces.com/contest/1988/submission/270901433)。
另一种求法是枚举作为 $l$ 或 $r$ 的 $i$，从 $i - 1$ 开始跳 $l$ 直到值大于 $a_i$，从 $i + 1$ 开始跳 $r$ 直到值大于 $a_i$，得到两条链（笛卡尔树上左儿子的右链和右儿子的左链），在链上双指针求出这些位置的 $l_2$ 和 $r_2$。[代码](https://codeforces.com/contest/1988/submission/270902181)。这个求法虽然写起来简单，但无法像上一种求法一样扩展至 $l_k, r_k$。
看了一下官方题解，大致是这样的：用所有区间减去以 $p$ 为一端且另一端在 $[l + 1, r - 1]$ 外的区间（在笛卡尔树上向下 DFS 时顺便维护），减去 $[l + 1, r - 1]$ 的子区间（容易计算），加上 $[l + 1, p - 1]$ 的子区间（容易计算），加上 $[p + 1, r - 1]$ 的子区间（容易计算），再加上左端点在 $[l + 1, p - 1]$ 且右端点在 $[p + 1, r]$ 的区间。最后一部分再分成左端点在左儿子 $ls$ 及其左侧且右端点在右儿子 $rs$ 及其右侧的区间（容易计算），和剩下的部分。剩下的部分可以在 $ls + 1\sim p - 1$ 的后缀最小值序列（左儿子的右链）和 $p + 1\sim rs - 1$ 的前缀最小值序列（右儿子的左链）上双指针计算。