https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c
解法
https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/1997374
今回の問題はCHTを知っていれば解ける。
各iについて全てのjについての「a[j] + (j - i)^2」の最小値が答えになる。
a[j] + (j - i)^2 = a[j] + j^2 - 2ij + i^2
と変形ができる。ここでjで変化するのは「-2ji + (a[j] + j^2)」の部分。
これはiについて1次関数の形になる。
よって、N個の1次関数があり、全ての1次関数のiに値を代入した時の最小値が高速に得られればいい。
これはCHTそのままである。
その為、CHTに「-2ji + (a[j] + j^2)」を全部入れて、iを代入した時の最小値をそれぞれ求めて答えるだけ。
int N; ll A[201010]; CHT<ll> cht; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; cht.init(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) cht.add(-2 * i, A[i] + 1LL * i * i); rep(i, 0, N) { ll ans = cht.get(i) + 1LL * i * i; printf("%lld\n", ans); } }