yukicoder : No.2220 Range Insert & Point Mex

これはそこまで難しくないかな。
https://yukicoder.me/problems/no/2220

問題

沢山の整数集合S[i]がある。
これらに対し、以下の手順を計N通り行う。
S[L[i]]...S[R[i]]に、A[i]を加える。

ここで、クエリXが与えられる。
集合S[X]のmex値を求めよ。

解法

mexとしてあり得る値は、0～Nの(N+1)通りである。
そこで、X及びL[i],R[i]をソートして、Sに含まれる値とその登場頻度及び、Sに含まれないN以下の値の集合を持ちながら走査しよう。

int N;
int L[101010],R[101010],A[101010];
int Q;
int X[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> ev;
	FOR(i,N) {
		cin>>L[i]>>R[i]>>A[i];
		if(A[i]>200000) continue;
		ev.push_back({L[i],i});
		ev.push_back({R[i],2000000+i});
	}
	set<int> alone;
	map<int,int> M;
	FOR(i,202020) alone.insert(i);
	
	cin>>Q;
	FOR(i,Q) {
		cin>>X[i];
		ev.push_back({X[i],1000000+i});
	}
	
	sort(ALL(ev));
	FORR2(a,i,ev) {
		if(i<1000000) {
			alone.erase(A[i]);
			M[A[i]]++;
		}
		else if(i>=2000000) {
			i-=2000000;
			M[A[i]]--;
			if(M[A[i]]==0) alone.insert(A[i]);
		}
		else {
			cout<<*alone.begin()<<endl;
		}
	}
	
}

まとめ

★3の中でも割と緩め。