Kodamanと愉快な仲間たち : O - Illumination2

よくこんだけ問題作ったなぁ…。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/illumination2

問題

01で構成されるN要素の数列が与えられる。
また、M個の区間が与えられる。
いずれかの区間を選択し、数列中その区間の0/1を反転させるということを任意回数行えるとする。

数列をすべて1にできるか判定せよ。

解法

左端から値を見ていき、0を見つけるたびに、そこを左端とする区間で反転することを考える。
ただしそのような区間が無ければ1にできない、という結果になる。

ここで、左端が同じ区間が複数ある場合問題となるが、[L,R]と[L,R'] (R＜R')という区間があった場合、これは[L,R]と[R+1,R']の2つの区間を個別に選択できるのと同じ意味であるので、区間を分解できる。
これを繰り返すと、結局左端毎に取れる右端が一意に確定する。

int N,M;
string S;
vector<int> E[505050];
int TE[505050];
int can[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(TE);
	cin>>N>>M>>S;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y);
		can[x-1]++,can[y]++;
	}
	set<int> T;
	int pre=-1;
	FOR(i,N) if(can[i]) {
		FORR(e,E[i]) T.insert(e);
		if(pre>=0 && TE[pre]>i) {
			T.insert(TE[pre]);
			TE[pre]=i;
		}
		while(T.size() && *T.begin()<=i) T.erase(T.begin());
		if(T.size()) {
			TE[i]=*T.begin();
			T.erase(T.begin());
			pre=i;
		}
	}
	
	int cur=0;
	while(cur<N) {
		if(TE[cur]==-1) {
			if(S[cur]=='0') return _P("No\n");
			cur++;
		}
		else {
			int C[2]={};
			for(i=cur;i<TE[cur];i++) C[S[i]-'0']++;
			if(C[0]&&C[1]) return _P("No\n");
			cur=TE[cur];
		}
	}
	_P("Yes\n");
}

まとめ

これは過去にどこかで見てそう。