就是把每个区间是否翻转看成一个变量 $x_i$ 然后从前向后贪心翻，给每个区间赋个随机权值然后用线性基判一下是否会线性相关出矛盾。但是 WA 了。。。

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef unsigned long long ull;
#define pii pair<ull,int>
#define fi first
#define se second
const int N=2e5+5;
int n,m;char s[N],t[N],a[N];ull b[N];
ull c1[70];bool c2[70];
il void add(ull v,int w){
	if(!v) return ;
	for(int i=63;i>=0;--i){
		if((v>>i)&1){
			if(!c1[i]){c1[i]=v,c2[i]=w;return ;}
			v^=c1[i],w^=c2[i];
		}
	}
}
il int check(ull v){
	if(v==0) return 0;
	ull x=0;int w=0,c,d;
	for(int i=63;i>=0;--i){
		if(!c1[i]) continue;
		c=((v>>i)&1),d=((x>>i)&1);
		if(c!=d) x^=c1[i],w^=c2[i];
	}
	if(x==v) return w;
	else return -1;
}
int x,y,z,u,v;ull w;
int main(){
	//freopen("c1.in","r",stdin);
	//freopen("c1.out","w",stdout);
	mt19937_64 rnd(time(0));
	scanf("%d%d%s%s",&n,&m,s+1,t+1);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);w=rnd();
		b[x]^=w,b[y+1]^=w;
	}
	for(int i=1;i<=n;++i) b[i]^=b[i-1];
	for(int i=1,j;i<=n;++i){
		if(s[i]==t[i]){a[i]=s[i];continue;}
		j=i;while(j<n && b[j+1]==b[i]) ++j;
		x=check(b[i]);
		if(x==-1){
			if(s[i]=='0'){add(b[i],1);for(int k=i;k<=j;++k) a[k]=t[k];}
			else{add(b[i],0);for(int k=i;k<=j;++k) a[k]=s[k];}
		}
		else{
			if(x==1){add(b[i],1);for(int k=i;k<=j;++k) a[k]=t[k];}
			else{add(b[i],0);for(int k=i;k<=j;++k) a[k]=s[k];}
		}
		i=j;
	}
	printf("%s",a+1);
	return 0;
}
/*
5 3
10110
01001
1 3
2 3
3 4

3 2
011
100
1 3
1 2
*/