CF1762F Good Pairs
Alex_Wei
·
·
题解
首先，如果路径先下降后上升，即 a_x > a_y < a_z，则 x 可达 z。因此，路径上所有点的权值 单调不降 或 单调不增。这两个问题解法几乎完全相同，且仅在 a_i = a_j 时重叠。接下来只讨论单调不降的情况，此时 a_i \leq a_j。
- 若 a_j\leq a_i + k，则 i 直接可达 j。
- 若 a_j > a_i + k，则 i 会跳到第一个满足 a_i\leq a_{p_i}\leq a_i + k 的后继 p_i，这样显然是不劣的。
对权值从大到小扫描线，用 set 维护权值落在 [v, v + k] 的所有位置，即可快速求出 p_i。
关于求答案，难道我们要求出 a_{p_i} 所有 a_j > a_i + k 且可达的位置 j 吗？其实不然。考虑以 l = p_i 的合法对数量，一定满足 a_r \geq a_{p_i}。而 a_i\leq a_j < a_{p_i} 的 j 是一步可达的，所以 l = i 的合法对数量，即 l = p_i 的合法对数量，加上 j > i 且 a_i\leq a_j < a_{p_i} 的 j 的数量，容易 DP + BIT 维护。
时间复杂度 \mathcal{O}(n\log V)。代码。