Official

D - Range Set Insertion Query Editorial by MMNMM Editorial for printing


\(N\) 個の集合 \(S _ 1,S _ 2,\ldots,S _ N\) を時系列だと思うことで、問題は以下のように読み替えられます。

集合 \(S\) に対して \(Q\) 個の操作を行う。\(i\) 番目の操作は「\(L _ i\) 秒から \(R _ i+\dfrac12\) 秒までの間、\(S\) に \(X _ i\) を追加する」である。\(t\) 秒 \((1\le t\le N)\) における \(S\) の要素数をそれぞれ求めよ。

これはイベントソートの要領で解くことができます。 具体的には、「現在 \(X _ i\) を追加している操作の個数」を管理し、\(0\) が \(1\) になるときや \(1\) が \(0\) になるときに答えを更新すればよいです。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N, Q;
    cin >> N >> Q;
    vector<tuple<unsigned, unsigned, unsigned>> event;
    for (unsigned i{}; i < Q; ++i) {
        unsigned L, R, X;
        cin >> L >> R >> X;
        --L;
        --X;
        event.emplace_back(L, X, 1); // X を追加するイベント
        event.emplace_back(R, X, -1); // X を削除するイベント
    }
    event.emplace_back(N, 0, 0); // 番兵

    ranges::sort(event);
    vector<unsigned> counter(Q); // counter[i] := i を追加しているイベントがいくつあるか
    unsigned ans{}, now{};
    for (const auto &[t, x, v] : event) {
        while (t != now) {
            ++now;
            cout << ans << " ";
        }
        if (counter[x] == 0) ++ans; // 0 から増えたら答えを増やす
        counter[x] += v;
        if (counter[x] == 0) --ans; // 0 に減ったら答えを減らす
    }
    cout << endl;
    return 0;
}

posted:
last update: