codeflyer 2018 final B - 交通費

B: 交通費 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト | AtCoder

概略
N人が一直線に立っている。Qでcとdが与えられる

Xi−c

≤d のとき、

Xi−c

円

そうでないとき、d 円　お金がかかる。
何円かかるか毎クエリ答える

N 10^5

解法
累積和、近くの部分だけ二分探索でうまく探して足す。
番兵法を使おう

 public static void main(String[] args)
    {
        N = sc.nextInt();
        int Q = sc.nextInt();
        X = new int[N + 2];
        X[0] = -2000000001;
        X[N + 1] = 2000000001;
        for (int i = 1; i < N + 1; i++)
            X[i] = sc.nextInt();

        long[] sums = new long[N + 2];
        sums[0] = X[0];

        for (int i = 1; i < N + 2; i++)
            sums[i] = sums[i - 1] + X[i];

        for (int q = 0; q < Q; q++)
        {
            int c = sc.nextInt();
            int d = sc.nextInt();
            int m = lowerBound(X, c) - 1;//自分の左 -なら自分の左に数は存在しない
            int lbng = lowerBound(X, c - d) - 1; //左で、ngのインデックス -なら全部範囲内
            int rbok = upperBound(X, c + d) - 1;//右でで、最大のokなインデックス
            long res = -2 * d;//番兵の分

            //d円の者たち
            long dcou = 0;
            dcou += lbng + 1;
            dcou += N + 1 - rbok;
            res += dcou * d;

            //l
            long lsize = m - lbng;
            res += c * lsize - (sums[m] - sums[lbng]);

            //r
            long rsize = N + 2 - lsize - dcou;
            res += (sums[rbok] - sums[m]) - c * rsize;
            System.out.println(res);
        }
    }