CF2110F 题解

前言

很小清新的一道题。

思路

考虑什么样的数对会产生贡献。不妨设 $x<y$，那么 $f(x,y)=x+y\mod x$。一个很重要的观察是：$f(x,y)\in [x,2x)$。因此对于长为 $n$ 的有序序列 $a$，考虑答案下界：取 $x,y$ 分别为次大值和最大值，即 $x=a_{n-1},y=a_n$ 时，答案一定 $\geq a_{n-1}$。

分类讨论各种情况的贡献：

• 对于 $x\leq \frac{a_{n-1}}{2}$，其贡献上界小于这个下界，是没有意义的。
• 当 $x>\frac{a_{n-1}}{2}$ 时，若 $y\leq a_{n-1}$，此时因为 $x>\frac{y}{2}$，取模操作变成了减法！即 $f(x,y)=x+(y-x)=y$，因此同样对答案无法造成有效贡献。

于是我们发现 $y$ 永远是最大值。

• 对于前缀 $i$，若 $a_i$ 不是前缀 $\max$，只需要计算 $f(a_i,pre_i)$ 即可，其中 $pre_i$ 代表前缀 $i$ 个元素的最大值。否则，依旧考虑利用 $x>\frac{y}{2}$ 时取模实际上是减法，$f(x,y)=y$ 的性质。
• 若 $pre_{i-1}<a_i<2pre_{i-1}$，也就是 $a_i$ 更新了前缀 $\max$ 但并未翻倍时，取 $x=pre_{i-1},y=a_i$ 即可取得答案为 $a_i$。对于其他 $x$ 的取值，若 $x<\frac{a_i}{2}$，其上界 $<a_i$，无法造成贡献；否则贡献依旧为 $a_i$。
• 否则，$a$ 的值域有限，前缀 $\max$ 只会翻倍 $\log V$ 次。每次暴力计算 $a_i$ 与前面所有元素的贡献即可。

复杂度 $\mathcal{O}(n\log V)$。