codeforces 1575M Managing Telephone Poles

假设固定了 \((x, y)\)，考虑其和 \((x', y')\) 的距离 \((x - x')^2 + (y - y')^2 = x^2 - 2xx' + x'^2 + y^2 - 2yy' + y'^2 = (x^2 + y^2) + (-2xx' + x'^2) + (-2yy' + y'^2)\)。
第一个括号内的式子是个定值，不用管；第二三个式子都是一次函数的形式，但是这是个二元组，放在一起看很难处理。
于是考虑固定一边，比如固定下 \(x\)，式子拆成 \(y^2 + (-2yy' + y'^2 + (x - x')^2)\)，即把 \((x - x')^2\) 这个东西也当作一个定值加进一次函数。

但是看起来右边的括号会有 \(O(nm)\) 种情况还是优化不下去。
考虑去除掉不优的状态。
发现对于 \((x_1, y'), (x_2, y')\)，如果 \(|x_1 - x| \le |x_2 - x|\)，\((x_2, y')\) 这个点是无用的。
因为此时 \((y - y')^2\) 相同而固定下了 \(x\) 又有 \((x_1 - x)^2\le (x_2 - x)^2\)，所以 \((x_1, y)\) 一定更优。
那么每个 \(y'\) 最多只会有一种情况，右边括号就只有 \(O(m)\) 种情况了。

时间复杂度 \(O(nm\log m)\)。

#include<bits/stdc++.h>
const int maxn = 2e3 + 10;
const int inf = INT_MAX;
int n, m;
char s[maxn][maxn];
int L[maxn][maxn], R[maxn][maxn];
struct seg {
    int k, b;
    int operator () (const int &x) {return k * x + b;}
} tr[maxn];
int ls[maxn], rs[maxn], tot, rt;
inline void insert(int &k, seg x, int l = 0, int r = m) {
    if (! k) {tr[k = ++tot] = x, ls[k] = rs[k] = 0; return ;}
    int mid = (l + r) >> 1;
    if (x(mid) < tr[k](mid)) std::swap(x, tr[k]);
    if (l == r) return ;
    if (x(l) < tr[k](l)) insert(ls[k], x, l, mid);
    if (x(r) < tr[k](r)) insert(rs[k], x, mid + 1, r);
}
inline int qry(int k, int x, int l = 0, int r = m) {
    if (! k) return inf;
    if (l == r) return tr[k](x);
    int mid = (l + r) >> 1;
    return std::min(tr[k](x), x <= mid ? qry(ls[k], x, l, mid) : qry(rs[k], x, mid + 1, r));
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) scanf("%s", s[i]);
    for (int j = 0; j <= m; j++) {
        for (int i = 0, p = -1; i <= n; i++) s[i][j] == '1' && (p = i), L[i][j] = p;
        for (int i = n, p = -1; ~ i; i--) s[i][j] == '1' && (p = i), R[i][j] = p;
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++) {
        rt = tot = 0;
        for (int j = 0; j <= m; j++) {
            int d = std::min(L[i][j] == -1 ? inf : (i - L[i][j]), R[i][j] == -1 ? inf : (R[i][j] - i));
            if (d == inf) continue;
            insert(rt, seg{-2 * j, d * d + j * j});
        }
        for (int j = 0; j <= m; j++) ans += j * j + qry(rt, j);
    }
    printf("%lld\n", ans);
    return 0;
}