FII Code 2021 Round #2 : D. Endgame

問題文が若干わかりにくいな。
https://csacademy.com/contest/fii-code-2021-round-2/task/endgame/

問題

1次元の区間が複数与えられる。
共通部分を持つ区間同士は連結している、とみなし、連結した区間の数を数えることを考える。
今ここで、1つ任意の座標を指定し、その座標を含む区間をすべて削除できるものとする。
連結した区間数の最大値はいくつか。

解法

座標圧縮したうえで、削除位置を総当たりしよう。
その際、削除位置の左側に完全に含まれる連結区間と、削除位置の右側に完全に含まれる連結区間をそれぞれ数え上げ、その和を求めよう。
前者については、区間の右端に関し平面走査を行うことで解ける。
ある区間の右端に到達したら、過去に登場した右端のうち、走査中の区間の左端の右側にあるものについて連結する。
この作業はmultisetやstackを使い、既存の連結区間の右端の集合を持つことで処理できる。

int N;
ll L[101010],R[101010];
int ret[604040];
vector<ll> ev[604040];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<ll> cand;
	cand.push_back(-(5LL<<30));
	cand.push_back((5LL<<30));
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		cand.push_back(4*L[i]);
		cand.push_back(4*L[i]-2);
		cand.push_back(4*R[i]+2);
		L[i]=4*L[i]-1;
		R[i]=4*R[i]+1;
		cand.push_back(L[i]);
		cand.push_back(R[i]);
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	FOR(i,N) {
		L[i]=lower_bound(ALL(cand),L[i])-cand.begin();
		R[i]=lower_bound(ALL(cand),R[i])-cand.begin();
	}
	
	FOR(j,2) {
		FOR(i,cand.size()) ev[i].clear();
		FOR(i,N) ev[R[i]].push_back(L[i]);
		multiset<int> uniq;
		
		FOR(i,cand.size()) {
			FORR(e,ev[i]) {
				while(uniq.size()&&*uniq.rbegin()>=e) uniq.erase(*uniq.rbegin());
				uniq.insert(i);
			}
				
			if(j==0) {
				ret[i]+=uniq.size();
			}
			else {
				ret[cand.size()-1-i]+=uniq.size();
			}
		}
		
		
		FOR(i,N) {
			L[i]=cand.size()-1-L[i];
			R[i]=cand.size()-1-R[i];
			swap(L[i],R[i]);
		}
	}
	
	cout<<*max_element(ret,ret+cand.size())<<endl;
	
}

まとめ

途中だいぶ遠回りな実装をしてしまった。