Problem Statement
You are given an array $a$ of length $n$.
Let $f\left(x, y\right) = \left(x \bmod y\right) + \left(y \bmod x\right)$.
For each $i \in \left[1, n\right]$, you need to calculate:
$$\max\limits_{1 \leq j < k \leq i} f\left(a_j, a_k\right)$$
$n \leq 10^6, 1 \leq a_i \leq 10^9$
Tutorial
Fact 1
$f\left(x, y\right) \leq \max\left(x, y\right)$
First, if $x = y$, then $f\left(x, y\right) = 0$.
Now assume that $x < y$, then $f\left(x, y\right) = \left(x \bmod y\right) + \left(y \bmod x\right) = x + y - \left\lfloor y / x\right\rfloor \cdot x \leq y$.
Fact 2
We only need to consider the cases where either $a_j$ or $a_k$ is the prefix maximum.
Let $a_{mx}$ denote the prefix maximum.
Because of Fact 1, $f\left(a_j, a_k\right) \leq \max\left(a_j, a_k\right)$.
Let $p = \max\left(a_j, a_k\right)$
Now consider $f\left(p, a_{mx}\right)$. Since $p < a_{mx}$, we have $p \bmod a_{mx} = p$. Hence $f\left(p, a_{mx}\right) \geq p \geq f\left(a_j, a_k\right)$.
Fact 3
If $x < y < 2x$, then $f\left(x, y\right) = y$
$f\left(x, y\right) = \left(x \bmod y\right) + \left(y \bmod x\right) = x + y - \left\lfloor y / x\right\rfloor \cdot x$
Since $\left\lfloor y / x\right\rfloor = 1$, then $f\left(x, y\right) = y$.
Therefore, we can handle the new added value $a_i$ in three cases:
- $a_i \leq a_{mx}$, $a_{mx}$ has not been updated. Update the answer with $f\left(a_{mx}, a_i\right)$.
- $a_{mx} < a_i < 2a_{mx}$, Update $a_{mx}$. According to Fact 3, the answer is $a_i$.
- $a_i \geq 2a_{mx}$, This happens at most $\log V$ times, so we can simply iterate through the array and update the answer.
Time complexity: $O\left(n \log V\right)$.
Code
struct VOIDENGINE {
VOIDENGINE([[maybe_unused]] int TEST_NUMBER) {
int n; bin(n);
vi a(n); bin(a);
int mx = a[0];
int tar = 0;
auto f = [](int x, int y) { return x % y + y % x; };
eu(i, n) {
if (a[i] <= mx) ckmax(tar, f(a[i], mx));
else if (mx < a[i] && a[i] < 2 * mx) tar = mx = a[i];
else {
mx = a[i];
eu(j, i) ckmax(tar, f(mx, a[j]));
}
cout << tar << " \n"[i == n - 1];
}
}
};
void VOIDSPECTRE([[maybe_unused]] int argc, [[maybe_unused]] char* argv[]) {
}