到 衡 实 了

今天期中考完，考的很垃圾，没啥可总结的，补一道前几天的题的口胡

2022NOIP A层联测19

T4 术劣

在地理自习上想完了细节。

感觉智力很下降，经典 trick 没有想起来。

等差数列肯定就是从公差入手。先考虑给定一个序列如何快速判定它是否为等差数列并求出它的公差。

可以口胡一个性质：如果这个序列排序后为等差序列，那么 \(\gcd(|a_2 - a_1|, |a_3 - a_2|, \cdots, |a_n - a_{n - 1}|)\) 就是它的公差。

证明：

考虑归纳法。首先假如当前的序列为等差序列，考虑加一个数会发生什么。
如果加上这个数后仍为等差数列，那么 \(\gcd(w, |a_n - a_{n - 1}|)\) 一定还是 \(w\)。
如果加上这个数后不再是等差数列，那么之后如果再变成等差数列，那么公差变小，并且 \(\gcd(g, |a_n - a_{n - 1}|) = \gcd(|a_n - a_{n - 1}| \bmod g, g)\)，那么一定等于之后可能成为的公差。

那么这个式子就很强了。首先我们注意到，固定左端点，那么对于每一个右端点，它的公差最多只会更改 \(\log n\) 次，那么对于所有的序列来说，公差只有可能有 \(O(n \log n)\) 种。

下面的问题就是，如果判定它是不是等差数列。发现这东西跟值域上覆盖连续区间差不多，我们可以用经典 trick 转化成求 \((\max a_i - \min a_i) - len = 0\)，对于这个问题我们可以知道值域的连续长度应当是 \(w \times (r - l)\)，于是就经典的维护 \(\max a_i - \min a_i - w \times (r - l)\) 的最小值与最小值个数。

扫描线，直接维护后面那个东西。如果 \(w\) 被改变，那么暴力往下修改即可，因为 \(w\) 总变化量是 \(O(n \log n)\) 的，于是暴力修改总复杂度就是 \(O(n \log^2 n)\)。实现的时候需要维护一下 \(w\) 的连续段，每次暴力计算一下即可。