AtCoder ABC #155 : F - Perils in Parallel

すまぬ…。
https://atcoder.jp/contests/abc155/tasks/abc155_f

問題

N個の電球の位置とオンオフの状態が与えられる。
M個のスイッチがあり、各スイッチを切ると、ある区間の電球のオンオフが反転する。
全電球オフにするには、どのスイッチを切ればよいか。

解法

実は同種の問題を最近解いているのだが、こちらは復元パートがない。
この手法をとるとO(M^2)かかってTLEする。
Kodamanと愉快な仲間たち: O - Illumination2 - kmjp's blog

そこで別解法を取る。
まず座標圧縮は済ませておこう。

(座標圧縮は済んでいるとして)スイッチiにより[L[i],R[i]]のオンオフが反転するということは、L[i]以降を反転したうえでR[i]+1以降を反転させるのと等しい。
そこで、まず元の電球の状態についてオンオフの差分の数列を作っておこう。
隣接する電球と差分があれば1、なけれれば0とする。
こうすると、スイッチはこの数列において２か所の0、1を反転させるものとなる。

そこで、(N+1)頂点のグラフを考え、各スイッチに対応してL[i]-(R[i]+1)間を結ぼう。また、さらに各連結成分で全域木を構成しておく。
あとは各連結成分において、「辺の両端を0/1反転する」ということを繰り返し木の全頂点の値を0にすればよいので、DFSで処理できる。

int N,M;
int A[101010],B[101010];
int C[101010];
int L[202020],R[202020];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;
vector<pair<int,int>> E[202020];
vector<int> ret;

void dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e.first!=pre) {
		dfs(e.first,cur);
		if(C[e.first]) {
			ret.push_back(e.second);
			C[e.first]^=1;
			C[cur]^=1;
		}
	}

}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> Xs;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		Xs.push_back(A[i]);
	}
	Xs.push_back(1<<30);
	sort(ALL(Xs));
	FOR(i,N) {
		x=lower_bound(ALL(Xs),A[i])-Xs.begin();
		C[x]=B[i];
	}
	for(i=N;i>=1;i--) C[i]^=C[i-1];
	
	
	FOR(i,M) {
		cin>>L[i]>>R[i];
		L[i]=lower_bound(ALL(Xs),L[i])-Xs.begin();
		R[i]=lower_bound(ALL(Xs),R[i]+1)-Xs.begin();
		if(uf[L[i]]!=uf[R[i]]) {
			E[L[i]].push_back({R[i],i+1});
			E[R[i]].push_back({L[i],i+1});
			uf(L[i],R[i]);
		}
	}
	FOR(i,N+1) if(uf[i]==i) {
		dfs(i,i);
		if(C[i]) return _P("-1\n");
	}
	cout<<ret.size()<<endl;
	sort(ALL(ret));
	FORR(r,ret) cout<<r<<" ";
	cout<<endl;
}

まとめ

区間に対し反転させる問題は、prefixまたはsuffix 2か所を反転させると考えると楽になることがあるね。