Codeforces 799F Beautiful fountains rows

题面在这里

题意：有一\(N\times M\)的01矩阵，第i行的\([l_i,r_i]\)为1，区间\([L,R]\)是合法的当且仅当每一行在\([L,R]\)中出现奇数次，求所有合法区间的长度和

​

首先考虑\([L,R]\)合法，每一行都需要出现奇数次

这个看起来可以用异或乱搞

给每行赋一个随机权值，看作许多在一维空间分布的带权线段

通过差分可以得到以下数组：

• \(a[i]\)：所有在i位置出现过奇数次的线段异或和
• \(s[i]\)：\(a[i]\)的前缀异或和
• \(A[i]\)：左端点为i的线段异或和
• \(d[i]\)：\(A[i]\)的前缀异或和（左端点小于等于i的线段异或和）

对于区间\([L,R]\)，如果\(s[R]\text{^}s[L-1]=S\)，其中S表示区间中出现过的线段异或和，就可以认为是合法的

\(d[R]\text{^}d[L]\)表示\(l_i \in (L,R]\)的线段异或和

那么\(d[R]\text{^}d[L]\)比S少了\(l_i\le R,r_i\ge L\)的线段，其实少了\(a[L]\)

那么\(S=d[R]\text{^}d[L-1]\text{^}a[L]=s[R]\text{^}s[L-1]\)

移相整理得\(s[L]\text{^}d[L]=s[R]\text{^}d[R]\)

用MAP搞之

​

注意这样统计其实会把没有线段的区间判定为合法

最后减去空区间即可

​

示例程序：

#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
#define c(x) ((x)*((x)+1)/2)

const int maxn=200005;
int n,m;
ull a[maxn],A[maxn],s[maxn],d[maxn],ans;
map<ull,ull> num,sum;
int main(){
	srand(998244353);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		int x,y;scanf("%d%d",&x,&y); ull w=(ull)rand()*rand()*rand()+(ull)rand()*rand()+rand();
		a[x]^=w;a[y+1]^=w; A[x]^=w;
	}
	for (int i=1;i<=m;i++)
	 a[i]^=a[i-1],s[i]=s[i-1]^a[i],d[i]=d[i-1]^A[i];
	for (int i=1;i<=m;i++){
		ull w=s[i]^d[i];
		num[w]++;sum[w]+=i-1;
		ans+=num[w]*i-sum[w];
	}
	for (int i=1,j=0;i<=m;i++)
	 if (a[i]==0) ans-=c((ull)i-j);
	 else j=i;
	printf("%lld",ans);
	return 0;
}