abc155F题解

abc155F
题意:
给定\(n\)个灯泡的位置\(a_i\)和状态\(b_i(0/1)\)。给定\(m\)个开关控制区间\([l_i,r_i]\)中所有的灯泡，即使用这个开关会使\([l_i,r_i]\)中所有的灯泡的状态都取反。问能否使这\(n\)个灯泡的状态都变成\(0\)，如果可以，输出一种方案，否则，输出\(-1\)。
思路：
神仙转化题。
第一步转化，将得到\(b_i\)的异或差分数组\(c_i=\left\{\begin{matrix} b_i & i=1 \\ b_i\oplus b_{i-1} & i>1 \end{matrix}\right.\)，这样区间修改就变成了对\((l_i,r_i+1)\)这个点对进行修改。
第二步转化，将点\(l_i\)和点\(r_i+1\)连一条无向边，问题就变成了在一个无向图中选一些边，对每一条被选边的两个端点的状态都取反，使最终每个点的状态都是\(0\)。
第三步转化，对于一个环上的边，这些边一定不会都被选，因为如果都选了，状态相当于没变，所以最后选出来的边组成的一定是一个森林。并且对于任意一种生成树无解，则这个无向图也一定无解。所以这里就直接找出任意一种生成树（或生成树森林），对其完成第二步转化中的任务即可。这里要注意一下有的点会与点\(n+1\)连边，这些点可以是任意状态。
代码：

#include<iostream>
#include<algorithm>
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n,m;
struct node{
	int a,b;
}d[100010];
bool cmp(node x,node y){
	return x.a<y.a;
}
struct nod{
	int l,r;
	int p;
}c[200010];
struct nde{
	int to;
	int nxt;
	int id;
	int p;
}edge[400010];
int head[200010],tot;
void addedge(int u,int v,int id){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].id=id;
	head[u]=tot;
}
int f[200010];
int cha(int u){
	while(u!=f[u]){
		u=f[u]=f[f[u]];
	}
	return u;
}
int vis[200010];
int fa[200010];
int pan[200010];
int p;
void dfs(int u){
	if(pan[u]!=0){
		p=pan[u];
	}
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(vis[v]==1){
			continue;
		}
		fa[v]=i;
		dfs(v);
		if(d[v].b==1){
			edge[i].p=1;
			d[v].b=0;
			d[u].b^=1;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		d[i].a=kd();d[i].b=kd();
		f[i]=i;
	}
	sort(d+1,d+n+1,cmp);
	for(int i=n;i>=2;i--){
		d[i].b^=d[i-1].b;
	}
	for(int i=1;i<=m;i++){
		c[i].l=kd();c[i].r=kd();
		int l=1,r=n;
		while(l<r){
			int mid=(l+r)/2;
			if(d[mid].a<c[i].l){
				l=mid+1;
			}
			else{
				r=mid;
			}
		}
		c[i].l=l;
		l=1;r=n;
		while(l<r){
			int mid=(l+r+1)/2;
			if(d[mid].a>c[i].r){
				r=mid-1;
			}
			else{
				l=mid;
			}
		}
		c[i].r=r;
	}
	for(int i=1;i<=m;i++){
		if(c[i].r==n){
			pan[c[i].l]=i;
			continue;
		}
		if(cha(c[i].l)!=cha(c[i].r+1)){
			addedge(c[i].l,c[i].r+1,i);
			addedge(c[i].r+1,c[i].l,i);
			f[cha(c[i].l)]=cha(c[i].r+1);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			p=0;
			dfs(i);
			if(d[i].b==1){
				if(p==0){
					cout<<-1;
					return 0;
				}
				else{
					c[p].p=1;
					p=c[p].l;
					while(p!=i){
						edge[fa[p]].p^=1;
						p=edge[fa[p]%2==0?fa[p]-1:fa[p]+1].to;
					}
				}
			}
		}
	}
	for(int i=1;i<=tot;i++){
		if(edge[i].p==1){
			c[edge[i].id].p=1;
		}
	}
	int cnt=0;
	for(int i=1;i<=m;i++){
		if(c[i].p==1){
			cnt++;
		}
	} 
	cout<<cnt<<endl;
	for(int i=1;i<=m;i++){
		if(c[i].p==1){
			cout<<i<<" ";
		}
	}
	return 0;
}