交通費 [codeFlyer （bitFlyer Programming Contest） B]

https://beta.atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b

前提知識

• 累積和

考察過程

1. 絶対値というのが面倒なので、分けておく。0≦X[i]-c≦dのときX[i]-c円、-d≦X[i]-c＜0のときc-X[i]円
2. Q個のクエリがあるので、O(1)かO(logN)で処理する必要がある
3. 支給額は3種類ある「0≦X[i]-c≦d」「-d≦X[i]-c＜0」「それ以外」
4. lower_boundとかでどこからどこまでがこの支給額かわかりそう
5. X[L]...X[R]が「0≦X[i]-c≦d」の支給額なら(X[L] + ... + X[R]) - c * (R-L+1)で一括計算できる
6. 累積和使えば間に合いそう

解法

https://beta.atcoder.jp/contests/bitflyer2018-final-open/submissions/2762883

各クエリについて「0≦X[i]-c≦d」「-d≦X[i]-c＜0」「それ以外」の3パターンの支給額をそれぞれ計算して答えよう。
考え方は難しくないのだが、実装がやばいので、色々な工夫を使って正確に書いていこう。
　
まずはしっかり場合分けしよう。
「0≦X[i]-c≦d」→「c≦X[i]≦d+c」
「-d≦X[i]-c＜0」→「-d+c≦X[i]＜c」
「それ以外」→「-inf＜X[i]＜-d+c」「d+c＜X[i]＜inf」
これで4つの区間に別れた。
ここから「全て『L≦x＜R』の形にしておくことでlower_boundで楽に分割できる」という工夫を使おう。
なので「-inf≦X[i]＜-d+c」「-d+c≦X[i]＜c」「c≦X[i]＜d+c」「d+c≦X[i]＜inf」としておこう。
計算的には問題無い。
　
さて、lower_boundで境界線を探すが、境界線は「-d+c」「c」「d+c」なので、それぞれlower_boundしてx,y,zとする。
すると、対応する区間は
「-inf≦X[i]＜-d+c」→[0, x)
「-d+c≦X[i]＜c」→[x, y)
「c≦X[i]＜d+c」→[y, z)
「d+c≦X[i]＜inf」→[z, N)
となる。
　
あとは、それぞれの区間について支給額を計算して総和をとると答え。
工夫として累積和はget関数を用意しておくといい。
バグらせない人も多いとは思うが、自分は毎回作っている。

int N, Q, X[101010]; ll sm[101010];
//---------------------------------------------------------------------------------------------------
ll get(int L, int R) { // [L, R]
    if (L > R) return 0;
    ll res = sm[R];
    if (L) res -= sm[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> X[i];
    sm[0] = X[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + X[i];

    rep(i, 0, Q) {
        int C, D; cin >> C >> D;

        int x = lower_bound(X, X + N, -D + C) - X;
        int y = lower_bound(X, X + N, C) - X;
        int z = lower_bound(X, X + N, D + C) - X;

        ll ans = 0;
        
        // (-inf, -d+c)
        ans += 1LL * D * x;

        // [-d+c, c)
        ans += 1LL * C * (y - x) - get(x, y - 1);

        // [c, d+c)
        ans += get(y, z - 1) - 1LL * C * (z - y);

        // [d+c, inf)
        ans += 1LL * D * (N - z);

        printf("%lld\n", ans);
    }
}