Paint the Fence [CSAcademy #61 C]

https://csacademy.com/contest/round-61/task/paint-the-fence/

N枚の連続した壁がある。
M人の職人がいる。
i番目の職人は[L[i],R[i]]を塗る。
各i番目の職人について、その職人がもし塗らず、他の職人が全て塗った場合に塗られていない壁の数を答えよ。

前提知識

• 累積和とimos法

解法

まず、全ての職人に壁を塗らせてみる。
これはimos法でやろう。
壁を塗ってもらった場合に塗られた回数が…

• 0回 : これはどうやっても塗られない
• 1回 : 職人の区間にこの壁があったら、塗られてない数が1つ増える
• 2回 : どうやっても塗られる

ので、0回の壁を数える（変数sm）
次に、各職人について、[L[i],R[i]]の1回だけ塗られている壁の個数が取得できれば、それとsmの和が答えになる。
これは、「chance[i] := [0,i]で1回だけ塗られている壁の個数」を累積和的に用意しておいて、chance[R[i]] - chance[L[i] - 1]で取ってこれる。

int N, M, L[101010], R[101010];
int imos[101010];
int chance[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> L[i] >> R[i];
    rep(i, 0, M) L[i]--;

    rep(i, 0, M) {
        imos[L[i]]++;
        imos[R[i]]--;
    }

    rep(i, 0, N) imos[i + 1] += imos[i];

    int sm = 0;
    rep(i, 0, N) if (imos[i] == 0) sm++;
    rep(i, 0, N) if (imos[i] == 1) chance[i] = 1;
    rep(i, 1, N) chance[i] += chance[i - 1];

    rep(i, 0, M) {
        int ans = sm + chance[R[i] - 1];
        if (L[i]) ans -= chance[L[i] - 1];
        printf("%d\n", ans);

    }
}