D - Range Set Insertion Query Editorial by YocyCraft


For each element \(1 \le x \le q\), let’s look at all sets such that we will insert \(x\) into. We can collect all ranges \([L_i, R_i]\) and merge all ranges with intersection, and add \(1\) to answers of their union. For any \(k\) ranges we can sort them by their left endpoint to get their union in \(O(k \log k)\), and do “add 1” operation in \(O(1)\) on the difference array of the answer. So the whole problem could be solved in \(O(n \log n)\).

#include <bits/stdc++.h>

using namespace std;

const char nl = '\n';
const char sp = ' ';
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

#define all(a) (a).begin(),(a).end()

void set_max(auto& x1,auto x2){
	x1=max(x1,x2);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	vector<vpii> evt(q);
	for(int i=0;i<q;i++){
		int l,r,x;
		cin>>l>>r>>x;
		x--;
		// we collect all ranges that we will insert number x into evt[x]
		evt[x].emplace_back(l,r);
	}
	vi ans(n+2,0);
	for(int t=0;t<q;t++){
		if(evt[t].empty()) continue;
		// sort all ranges in evt[x] by their left endpoint
		sort(all(evt[t]));
		vpii v0;
		for(auto [l,r]:evt[t]){
			if(v0.empty()){
				v0.emplace_back(l,r);
			}else if(l<=v0.back().second+1){
				// if the new range intersects with the range on the top of stack, 
				// we merge them in-place
				set_max(v0.back().second, r);
			}else{
				// otherwise we push the new range into the stack
				v0.emplace_back(l,r);
			}
		}
		for(auto [l,r]:v0){
			// do O(1) modification on the difference array
			ans[l]++;
			ans[r+1]--;
		}
	}
	for(int i=1;i<=n;i++){
		// reconstruct the answer array by prefix sum
		ans[i]+=ans[i-1];
		cout<<ans[i]<<sp;
	}
}