Official

D - Range Set Insertion Query Editorial by en_translator


By regarding the \(N\) sets \(S _ 1,S _ 2,\ldots,S _ N\) as a timeline, the problem can be interpreted as follows:

Perform \(Q\) operations on a set \(S\). The \(i\)-th operation is “insert \(X\) into \(X\) from time \(L _ i\) to time \(R _ i+\dfrac12\).” Find the number of elements in \(S\) at time \(t\) \((1\le t\le N)\).

This can be solved in the manner of event sort. Specifically, manage how many number of elements is asking to insert \(X _ i\). When the count changes from \(0\) to \(1\), or from \(1\) to \(0\), update the answer.

The sample code is the following.

#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); // Insert X
        event.emplace_back(R, X, -1); // Remove X
    }
    event.emplace_back(N, 0, 0); // Sentinel

    ranges::sort(event);
    vector<unsigned> counter(Q); // counter[i] := How many events asks to insert i?
    unsigned ans{}, now{};
    for (const auto &[t, x, v] : event) {
        while (t != now) {
            ++now;
            cout << ans << " ";
        }
        if (counter[x] == 0) ++ans; // If it increases from 0, increment the answer
        counter[x] += v;
        if (counter[x] == 0) --ans; // If it decreases to 0, decrement the answer
    }
    cout << endl;
    return 0;
}