鉄則本 A07 - Event Attendance (3Q, ★3)

いもす法！！

• 問題へのリンク

問題概要

日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。

各日の出席者数を求めよ。

制約

• 

解法

鉄則本の問題なので、本の方を参照！！

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int D, N;
    cin >> D >> N;
    
    // バケットの準備
    vector<int> bac(D + 1, 0);
    
    // いもす法の準備
    for (int i = 0; i < N; ++i) {
        int L, R;
        cin >> L >> R;
        --L;
        
        // 区間 [L, R) への加算は、差分をとると「L への加算」「R への減算」となる
        ++bac[L];
        --bac[R];
    }
    
    // 最後に累積和をとる
    for (int d = 0; d < D; ++d) {
        bac[d + 1] += bac[d];
    }
    
    // 出力
    for (int d = 0; d < D; ++d) {
        cout << bac[d] << endl;
    }
}