令 \(sum_i\) 表示 \(\sum \limits_{j=1}^{i} {a_j}\)。
则 \(g(i, j) = (sum_j - sum_i)\)。
\(f(i, j) = (i - j)^2 + g(i, j)^2 = (i - j) ^ 2 + (sum_i - sum_j) ^ 2\)
所以 \(f(i, j) = (i - j)^2 + (sum_i - sum_j)^2\)。
\(f(i, j)\) 很像两点间距离公式。
即求坐标为 \((i, sum_i)\) 和 \((j, sum_j)\) 两点的距离。
求 \(f(i, j)\) 的最小值，就是求这 \(n\) 个点中的最近点对。
因为 \(n \leqslant 10^5\)，朴素的 \(\mathcal{O}(n^2)\) 的暴力算法肯定过不去。
于是要求 \(\mathcal{O}(n \log n)\) 的时间复杂度。
我们可以使用分治进行求解。
如果不知道 \(\mathcal{O}(n \log n)\) 的分治求解平面最近点对的话，
请先完成这道题和这道题。
注意：
由于点 \(i\) 的纵坐标 \(y_i = sum_i\)，则 \(y_i \in [-10^9, 10^9]\)，最后的答案又是距离的平方，所以要开 long long。
代码：
const int N = 1e5, inf = 1e9 + 7;
int n;
ll b[N + 5], sum[N + 5];
struct Poll {
ll x, y;
} a[N + 5], tmp[N + 5];
ll read() {
ll ret = 0, sgn = 0;
char ch = getchar();
while (!isdigit(ch)) sgn |= ch == '-', ch = getchar();
while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
return sgn? -ret: ret;
}
bool cmp(Poll a, Poll b) {
return a.x < b.x;
}
void merge(ll l, ll r) {
ll mid = l + r >> 1, i = l, j = mid + 1;
for (ll k = l; k <= r; k++)
if (i <= mid && (j > r || a[i].y < a[j].y)) tmp[k] = a[i++];
else tmp[k] = a[j++];
for (ll i = l; i <= r; i++) a[i] = tmp[i];
}
ll sqr(ll x) {
return x * x;
}
ll dis(Poll a, Poll b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
ll dfs(ll l, ll r) {
if (l >= r) return inf;
if (l + 1 == r) {
if (a[l].y > a[r].y) swap(a[l], a[r]);
return dis(a[l], a[r]);
}
ll mid = l + r >> 1, xmid = a[mid].x;
ll d = min(dfs(l, mid), dfs(mid + 1, r));
merge(l, r);
ll tot = 0;
for (ll i = l; i <= r; i++)
if (sqr(a[i].x - xmid) < d) b[++tot] = i;
for (ll i = 1; i <= tot; i++)
for (ll j = i + 1; j <= tot && sqr(a[b[i]].y - a[b[j]].y) < d; j++)
d = min(d, dis(a[b[i]], a[b[j]]));
return d;
}
int main() {
n = read();
for (ll i = 1; i <= n; i++) sum[i] = read();
for (ll i = 1; i <= n; i++) sum[i] += sum[i - 1];
for (ll i = 1; i <= n; i++) a[i].x = i, a[i].y = sum[i];
cout << dfs(1, n) << endl;
return 0;
}