题解：CF2110F Faculty

不失一般性的，我们设 $x \le y$。

从最简单的情况考虑，当 $x = y$ 时，$f(x,y) = 0 + 0 = 0$。以下均为 $x < y$ 的情况，推推式子可知：

由于 $x < y$，式子可以进一步化简：

由 $x < y$ 可知 $\lfloor\frac{y}{x}\rfloor \ge 1$，于是可以得到以下观察：

分析可知，当 $x \mid y$ 时不等式左侧取等；当 $x < y < 2x$ 时不等式右侧取等。

接下来考虑对于任意前缀长度为 $k$ 的答案是怎么取到的。当 $n = 1$ 时答案显然为 $0$，$n = 2$ 时为 $a_1 \bmod a_2 + a_2 \bmod a_1$。对于 $n \ge 3$ 的情况，考虑 $f(x,y)$ 与 $f(y,z)$ 满足 $x \le y \le z$，由不等式可知 $x \le f(x,y) \le y \le f(y,z) \le z$，因此可以证明前缀长度为 $k$ 的最大值里一定有一个数取到 $\max \limits_{i = 1}^k\{a_i\}$。

再由不等式可知存在 $y \ge 2x$ 的情况时才会使得答案变得不确定，而这种情况最多只会有 $\log$ 次，因此直接暴力更新即可，总时间复杂度 $O(n \log n)$。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void solve ()
{
    int n = read ();
    vector <int> a (n + 1),ans (n + 1,0);
    for (int i = 1;i <= n;++i) a[i] = read ();
    int mx = a[1];
    for (int i = 2;i <= n;++i)
    {
        if (a[i] > mx)
        {
            if (a[i] >= mx * 2) {for (int j = 1;j < i;++j) ans[i] = max (ans[i],a[i] % a[j] + a[j] % a[i]);}
            else ans[i] = a[i];
            mx = a[i];
        }
        else ans[i] = max (ans[i - 1],mx % a[i] + a[i] % mx);
    }
    for (int i = 1;i <= n;++i) printf ("%d ",ans[i]);
    puts ("");
}