Official
D - Range Set Insertion Query Editorial
by
D - Range Set Insertion Query Editorial
by
MMNMM
\(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;
}
