题目链接：LOJ 2020

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$（可能是负数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$，其中 $n$ 为每个手环的装饰物个数，第一个手环的 $i$ 号位置装饰物亮度为 $x_i$，第二个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为：

$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

数据范围：$1 \le n \le 5 \times 10 ^4$，$1 \le a_{i} \le m \le 100$。

Solution

我们将答案的式子写出来并展开：

$$ \begin{align*} \text{answer} & = \sum_{i = 1} ^ {n} (x_{i} - y_{i} + c) ^ {2} \\ & = \sum_{i = 1} ^ {n} (x_{i} ^ {2} + y_{i} ^ {2} + c ^ 2 + 2c(x_{i} - y_{i}) - 2 x_{i} y_{i} ) \\ & = \sum_{i = 1} ^ {n} (x_{i} ^ {2} + y_{i} ^ {2}) + nc ^ {2} + 2c \left(\sum_{i = 1} ^ {n} (x_{i} - y_{i}) \right) - 2 \sum_{i = 1} ^ {n} a_{i} b_{i +k} \end{align*} $$

其中 $k$ 为 $b$ 循环位移的长度（需要先把 $b$ 倍长）。

注意到除去 $2 \sum_{i = 1} ^ {n} a_{i} b_{i + k}$ 以外的部分是一个关于 $c$ 的二次函数的最小值是确定的。问题转化为求 $\sum_{i = 1} ^ {n} a_i b_{i + k}$ 的最大值。如果我们把 $a$ 翻转一下，这个式子就是卷积形式。答案就是卷积后最高 $n$ 项的最大值。

时间复杂度：$\mathcal O(n \log n)$。

Code

/* 此处省略多项式模板 */

int main() {
    int n;
    scanf("%d%*d", &n);
    Vec A(n), B(n);
    int ans = 0, sum = 0;
    for (auto &x : A) scanf("%d", &x), ans += x * x, sum -= x;
    for (auto &x : B) scanf("%d", &x), ans += x * x, sum += x;
    int x1 = floor(1.0 * sum / n), x2 = ceil(1.0 * sum / n);
    ans += std::min(n * x1 * x1 - 2 * x1 * sum, n * x2 * x2 - 2 * x2 * sum);
    B.resize(B.size() << 1);
    std::copy(B.begin(), B.begin() + n, B.begin() + n);
    std::reverse(A.begin(), A.end());
    Vec F = A * B;
    int mx = *std::max_element(F.begin() + n - 1, F.begin() + n + n - 1);
    printf("%d\n", ans - (mx << 1));
    return 0;
}