题目概述

有 $m\times n$ 的矩阵，第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇数个好的元素，求所有合法 $[A,B]$ 的 $\sum B-A+1$ 。

解题报告

神仙套路题，我们先给每行的线段随机一个权值，然后用差分求出每列被线段覆盖的情况，然后就可以愉快的用异或值判断了。但是没有好的元素这个条件皮得很，我们可以先把没有好的元素的情况算成合法，最后删除不合法的情况（这种情况一定是连续的一片）。

把 $[L,R]$ 好的元素的奇偶情况拿下来，如果把出现过的好的元素奇偶情况反一下其实就是判断异或值是不是 $0$ 。关键问题就是如果求出 $[L,R]$ 中出现的好的元素的集合。

考虑 $d_i$ 表示 $L\le i$ 的线段的异或和，$a_i$ 表示覆盖 $i$ 列的所有线段的异或值（之前的差分数组），$sum_i$ 表示 $a_i$ 的异或前缀和。那么对于一个区间 $[A,B]$ ：

$sum_{B}\ xor\ sum_{A-1}$ 表示 $[A,B]$ 中好的元素的奇偶情况，$d_{B}\ xor\ d_{A}$ 表示 $A<L\le B$ 的线段的异或和，相比于与 $[A,B]$ 相交的线段少了 $L\le A,R\ge A$ 的这些线段。

你会发现少掉的其实就是 $a_A$ ，所以 $sum_{B}\ xor\ sum_{A-1}=d_B\ xor\ d_A\ xor\ a_A$ 。

那么也就是 $sum_B\ xor\ d_B=sum_A\ xor\ d_A​$ ，map统计一下就好了。

示例程序

#include<cstdio>
#include<cstdlib>
#include<unordered_map>
using namespace std;
typedef unsigned long long ULL;typedef long long LL;
const int maxn=200000;

int n,m;ULL val[maxn+5],a[maxn+5],d[maxn+5],sum[maxn+5];
unordered_map<ULL,LL> f;unordered_map<ULL,int> g;LL ans;

#define Rand() ((ULL)rand()*rand()*rand()+(ULL)rand()*rand()+rand())
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(srand(759405),scanf("%d%d",&m,&n),1),L,R;i<=m;i++)
        scanf("%d%d",&L,&R),val[i]=Rand(),a[L]^=val[i],a[R+1]^=val[i],d[L]^=val[i];
    for (int i=1;i<=n;i++) a[i]^=a[i-1],d[i]^=d[i-1],sum[i]=sum[i-1]^a[i];
    for (int i=1;i<=n;i++) f[sum[i]^d[i]]+=i-1,g[sum[i]^d[i]]++,ans+=(LL)g[sum[i]^d[i]]*i-f[sum[i]^d[i]];
    for (int i=1,L=1;i<=n;i++) if (!a[i]) ans-=(LL)(i-L+1)*i-(LL)(L-1+i-1)*(i-L+1)/2; else L=i+1;
    return printf("%lld\n",ans),0;
}