木の燃やし方 [yukicoder 913]

https://yukicoder.me/problems/no/913

前提知識

• 列の分割統治
• CHT

解説

https://yukicoder.me/submissions/391706

分割統治+CHTで解く。
こういう系の問題に初めて取り組む場合は、まずは「列の分割統治」と「CHT」について学ぼう。
この2つが理解できていれば、今回の想定解を理解するのは難しくない。
逆に理解できないと理解できない。よりかんたんな問題でなれることをおすすめする。

分割統治をしながら求めていく。
f(L, R) := [L,R)の区間で木iを燃やしたときの悲しさの最小値を考える
分割用にmd=(L+R)/2とする。
まず、分割前提でf(L,md)とf(md,R)は別途考えるとすると、
f(L,R)で考えるべきケースはmdを通るケースになる。
分割統治で使う考え方として、左側を全探索して、右側のまとめて考えるというのがある。
今回もこれで木iを左端として、右端を右側でまとめて考える。
この部分でCHTを使おう。
細かな式変形は公式解説が詳しい。
考えによっては自分のようにl-kではなく、l+1-kで考える必要があるので注意。
あとはセオリー通りにやっていこう。

自分の実装では実装を少しサボり反転して2回行っている。
このときは、mdをいじらないと反転しない場合と一致しないので、注意。

int N, A[201010];
ll B[201010];
//---------------------------------------------------------------------------------------------------
void f(int L, int R, vector<ll>& ans, bool isRev = false) {
    if (L + 1 == R) {
        chmin(ans[L], 1LL + A[L]);
        return;
    }

    int md = (L + R) / 2;
    if (isRev and (R - L) % 2 == 1) md++;
    f(L, md, ans, isRev);
    f(md, R, ans, isRev);

    ConvexHullDynamic cht;
    rep(i, md, R) cht.addLine(-2LL * (i + 1), 1LL * (i + 1) * (i + 1) + B[i]);
    
    ll mi = infl;
    rep(i, L, md) {
        ll cst = cht.getBest(i) + 1LL * i * i;
        if (i) cst -= B[i - 1];
        chmin(mi, cst);
        chmin(ans[i], mi);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<ll> normal(N, infl);
    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];
    f(0, N, normal);

    reverse(A, A + N);

    vector<ll> rev(N, infl);
    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];
    f(0, N, rev, true);

    rep(i, 0, N) printf("%lld\n", min(normal[i], rev[N - 1 - i]));
}