Silver Fox vs Monster [AtCoder Beginner Contest 153 F]

https://atcoder.jp/contests/abc153/tasks/abc153_f

前提知識

• 尺取り法
• imos法

解説

https://atcoder.jp/contests/abc153/submissions/9784254

何から手を付ければいいかわからないかもしれない。
全探索対象も無いし、最小値を求めよとか言われるし、
こういう場合は何か良い性質を見つけないといけない。
今回の問題では操作を貪欲に行うことができる。

モンスターを座標の昇順に並べた時に最も左にあるモンスターを左端として爆弾を使うことで、左端のモンスターを倒しつつ、
それよりも右にあるモンスターになるべく攻撃を当てることができる。
最も左にあるモンスターを倒せるだけ爆弾を使ったら、モンスターが1匹減るので、残りのモンスターたちについて同様の総和を行っていく。
これを行うことで爆弾の使用回数を最小化できる。
よって、モンスターは座標の昇順に並べておこう。

左端からモンスターを倒していくので、先頭から順番に処理していこう。
あるモンスターを倒すことを考えると、そのモンスターを左端として爆弾を使ったときに、どのモンスターまで爆弾が届くかを求める必要がある。
これには、尺取り法を使おう。
左端が単調増加していくと、右端も当然単調増加していく。よって、尺取り法が使える。

左端に対してcnt回爆弾を使うと、A×cntダメージ与えることができるが、このダメージ分を区間分に与えるのはどうすればいいだろうか。
このパートの解決が一番難しい。
遅延評価セグメントツリーを使うと、直感的にというか、必要操作そのままに解決することができる。
自分の解法では、imos法の考えを利用する。
ダメージ分を区間に与えるが、[L,R)の区間にダメージを加えたいときは、buf[L] += Acnt, buf[R] -= Acntとして、累積和を取ればよい。
よって、この増減は行おう。
累積和部分は、先頭から操作を行いながら、累積和を取っていくようにしよう。
こうすることで使用したい部分については既に正しい値が手に入りながら、区間に対する計算を動的に追加できる。
最初はよくわからないかもしれないが、区間の追加は、既に正しい値となっている部分（累積和が取られている部分）よりもあとになるため問題ない
ということを考えながら、処理の正当性を考えよう。

int N, D, A, X[201010], H[201010];
ll buf[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D >> A;
    rep(i, 0, N) cin >> X[i] >> H[i];

    D *= 2;

    vector<pair<int, int>> xh;
    rep(i, 0, N) xh.push_back({X[i], H[i]});
    sort(all(xh));

    ll ans = 0;
    int R = 0;
    rep(L, 0, N) {
        if (L) buf[L] += buf[L - 1];

        int x = xh[L].first;
        int h = xh[L].second;

        if (buf[L] < h) {
            chmax(R, L + 1);
            while (R < N and xh[R].first - x <= D) R++;

            ll d = h - buf[L];

            ll cnt = (d + A - 1) / A;

            buf[L] += cnt * A;
            buf[R] -= cnt * A;
            ans += cnt;
        }
    }

    cout << ans << endl;
}