Codeforces ECR #092 : F. Bicolored Segments

解いた記憶がだいぶない…。
https://codeforces.com/contest/1389/problem/F

問題

1次元の数直線上における区間がN個与えられる。
各区間は2色のうちいずれかで塗られている。

N個の区間の部分集合を考える。
その際、共有部分を持つ区間は、同色でなければならないとする。
条件を満たす部分集合の最大要素数を求めよ。

解法

手始めに座標は座標圧縮しておこう。
各区間について、終端の小さい順に処理する。
その際、区間加算・区間最大値を取れるSegTreeを2つ用意しよう。
それぞれ、今処理している区間と逆の色が存在する最大の座標に対する、条件を満たす区間の取り方の最大数である。

今、区間[L,R]を追加する場合、SegTree上逆の色がそれとはぶつからない[0,L]の範囲についてインクリメントすることになる。

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

int N;
ll L[202020],R[202020];
int T[202020];
SegTree_3<int,1<<20> S[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> X;
	X.push_back(-1);
	FOR(i,N) {
		cin>>L[i]>>R[i]>>T[i];
		L[i]=2*L[i];
		R[i]=R[i]*2+1;
		T[i]--;
		X.push_back(L[i]);
		X.push_back(R[i]);
	}
	sort(ALL(X));
	X.erase(unique(ALL(X)),X.end());
	vector<pair<int,int>> cand;
	FOR(i,N) {
		L[i]=lower_bound(ALL(X),L[i])-X.begin();
		R[i]=lower_bound(ALL(X),R[i])-X.begin();
		cand.push_back({R[i],i});
	}
	
	sort(ALL(cand));
	int ma=0;
	FORR(c,cand) {
		x=c.second;
		S[T[x]].update(0,L[x],1);
		y=S[T[x]].getval(0,R[x]);
		ma=max(ma,y);
		
		r=S[T[x]^1].getval(R[x],R[x]+1);
		if(y>r) S[T[x]^1].update(R[x],R[x]+1,y-r);
		
	}
	cout<<ma<<endl;
	
	
}

まとめ

定期的に書いていかないと、問題の記憶が薄れるな。