线段树+卷积
这个东西直接算不太好，但是合并两段结果却很方便，假设c[i]表示选i个数乘积的和，那么$a[i]=\sum_{j=0}^{i}{b[j]*c[i-j]}$
线段树维护即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + ;
const double pi = acos(-);
int n, len, ans, suma, sumb, mx = -1e9, m;
struct data {
double x, y;
data() {}
data(double _x, double _y) : x(_x), y(_y) {}
data friend operator - (const data &a, const data &b) {
return data(a.x - b.x, a.y - b.y);
}
data friend operator + (const data &a, const data &b) {
return data(a.x + b.x, a.y + b.y);
}
data friend operator * (const data &a, const data &b) {
return data(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
} a[N], b[N];
void fft(data *a, int len, int f) {
int n = << len;
for(int i = ; i < n; ++i) {
int t = ;
for(int j = ; j < len; ++j) {
if(i & ( << j)) {
t |= << (len - j - );
}
}
if(i < t) {
swap(a[i], a[t]);
}
}
for(int l = ; l <= n; l <<= ) {
int m = l >> ;
data w = data(cos(pi / m), f * sin(pi / m));
for(int i = ; i < n; i += l) {
data t = data(, );
for(int k = ; k < m; ++k, t = t * w) {
data x = a[k + i], y = t * a[i + k + m];
a[k + i] = x + y;
a[i + m + k] = x - y;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i) {
scanf("%lf", &a[i].x);
suma += a[i].x;
}
for(int i = ; i <= n; ++i) {
scanf("%lf", &b[i].x);
b[i + n].x = b[i].x;
sumb += b[i].x;
}
int c = floor((double)(sumb - suma) / n + 0.5);
for(int i = ; i <= n; ++i) {
a[i].x += c;
ans += a[i].x * a[i].x + b[i].x * b[i].x;
}
reverse(b + , b + * n + );
for(; << len <= * n; ++len);
fft(a, len, );
fft(b, len, );
for(int i = ; i < << len; ++i) {
a[i] = a[i] * b[i];
}
fft(a, len, -);
for(int i = n + ; i <= * n + ; ++i) {
a[i].x /= ( << len);
mx = max(mx, (int)(a[i].x + 0.1));
}
printf("%d\n", ans - * mx);
return ;
}