started in 2025.12.5 15:55。
CF1762F Good Pairs
给定一个长度为 \(n\) 的数组 \(a\)，问有多少对 \((l,r)\) 满足存在一个首尾是 \(l,r\) 的单增下标子序列满足相邻对应数之差绝对值不超过 \(k\)。
\(n \leq 5 \times 10^5,k,a_i \leq 10^5\)。
首先有一个简单的观察：这个子序列的数一定单调。
证明考虑把这个子序列的数每个数看成 \((i,a_i)\) 画到图上，连接相邻点。此时如果有一个谷或者一个峰，你可以直接把中间的删除。
接下来我们用“移动,走“表示这个子序列加数的过程，那么相当于是每次只可以在 \(|a_i-a_j| \leq k\) 的 \(i<j\) 从 \(i\) 移动到 \(j\)。
因此我们不妨只考虑不降的情况，即 \(a_l \leq a_r\) 的情况。不增的情况让所有数取一个负号即可。最后再减掉两者重复的部分即 \(a_l=a_r\) 的对数即可。
我们考虑从后往前扫，每次计算当前点作为 \(l\) 的情况下合法的 \(r\) 的个数。对 \(a_r\) 的值分类。
- 若 \(a_r \in [a_l,a_l+k]\)，则可以一步走到。
- 若 \(a_r>a_l+k\)，那么肯定是先走到最小的 \(p>i\) 满足 \(|a_p-a_l| \leq k\)，然后再看看能不能走到这些 \(a_r\)。
我们令 \(S_x\) 表示 \(x\) 往后走能走到的点的集合。
我们看看现在怎么计算方案数，第一部分是直观的，直接开 bit 算就行，设这种 \(r\) 的数量为 \(c\)。第二部分其实就是 \(S_p\)。那么 \(|S_l|=|S_p|+c\) 吗？并非如此，因为两者有重复部分，\(S_p\) 里面就包含了部分第一种的 \(a_r\)。可以发现去掉这一部分是好做的，直接 bit 即可。
实际上你直接对 \(|S_x|\) 做 dp 即可。
马上有场比赛，待会再写下后面的几个题。
要学的好多啊 /ll