题解：CF1762F Good Pairs

Abczzzzz · 2026-04-25 14:54:52 · 题解

重要观察：若 (l,r) 合法且 a_l\neq a_r，则一定存在严格上升或下降来连接 l 和 r 的方法。

证明：若有不单调的，则一定可以跳过峰或谷一步到达。

判掉相等的，对一个 r 往前分别考虑。以大于为例：

设蓝点为红点前面第一个大于它且差值不超过 k 的元素。则红点的答案分为了两部分：

• 一步到达：黄点（比蓝点小，且比红点大）。
• 两步及以上到达：可以证明，一定存在从蓝点走的路径。证明是简单的，若可以从黄点走，则一定可以从蓝点走。若可以从蓝点上面红点可以到达的点走，那蓝点可以到达那个点。

于是就做完了，答案等于两部分拼起来。