$选址$选址

$正解部分$正解部分

考虑什么时候 $i$i 会对 $x$x 产生贡献,
当 $c_i-\mid x-i{\mid }^2\>0$ci​−∣x−i∣2>0 时, 会产生贡献, 解方程得到 $x\in (i-\sqrt{c_i},i+\sqrt{c_i})$x∈(i−ci​ ​,i+ci​ ​) .

$\therefore$∴ 当 $x\in (i-\sqrt{c_i},i+\sqrt{c_i})$x∈(i−ci​ ​,i+ci​ ​) 时, $i$i 会对 $x$x 产生贡献 .

贡献为 $c_i-i^2+2ix-x^2$ci​−i2+2ix−x2,

• $c_i-i^2$ci​−i2 为常数, 可以直接使用一个差分数组处理 .
• $2i\ast x$2i∗x 的系数 $2i$2i 使用一个差分数组处理 .
• $1\ast x^2$1∗x2 的系数 $1$1 使用一个差分数组处理 .

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 100005;

int N;

ll C[maxn];
ll cf1[maxn];
ll cf2[maxn];
ll cf3[maxn];

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++) scanf("%lld", &C[i]);
        for(reg int i = 1; i <= N; i ++){
                int l = std::max(1, (int)(i*1.0-sqrt(C[i])+1.0));
                int r = std::min(N, (int)(i*1.0+sqrt(C[i])));
                cf1[l] += C[i] - 1ll*i*i,
                cf1[r+1] -= C[i] - 1ll*i*i;
                cf2[l] += 2ll*i, cf2[r+1] -= 2ll*i;
                cf3[l] ++, cf3[r+1] --;
        }
        ll a = 0, b = 0, c = 0;
        for(reg int i = 1; i <= N; i ++){
                a += cf1[i], b += cf2[i], c += cf3[i];
                printf("%lld ", a + b*i - c*i*i);
        }
        return 0;
}