题意

一个长度为$m$的序列
有$n$种数字，告诉你第$i$种数字出现的区间为$[l,r]$
然后问你有多少个区间，满足这个区间里至少有一种数字，并且出现过的数字必须出现奇数次

题解

这种奇数偶数的，多半都是用异或来搞
对于这种至于还特别大的，多半是给每一个数rand一个值来搞
但是这里有一个问题，就是出现过的数字的异或和怎么算
通过乱搞，我们发现
这个区间里面出现过的数字的异或和为
所有右端点在l右边的数^所有左端点在r左边的数^所有数
然后前缀和后缀和什么的随便搞搞就好了
最后再把空的区间减去就好了
但是这题，由于本身这个做法就容易冲突。。
所以要写双hash
但是我的hash太垃圾了，所以双hash还是WA了一发。。

CODE:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
typedef unsigned long long LL;
const LL N=200005;
LL n,m;
LL f[N];
LL sum[N];
LL g[N],h[N];//所有右端点在这右边的 所有左端点在这左边的 
//后一个东西可以写成所有右端点在l右边的球^所有左端点在r左边的球^所有球。
LL f1[N];
LL sum1[N];
LL g1[N],h1[N];//所有右端点在这右边的 所有左端点在这左边的 map<LL,LL> mp;
map<LL,LL> mp1;
LL cnt[N];
LL calc (LL x)
{return (1LL+x)*x/2LL;
}
int main()
{srand(200815147);scanf("%llu%llu",&n,&m);LL tot=0;for (LL u=1;u<=n;u++)   {f[u]=(rand()<<2)*(rand()*3)*rand()*(LL)200815143;tot^=f[u];f1[u]=(rand()<<5)|(rand()*3)^rand()*(LL)200815147;tot^=f1[u];}for (LL u=1;u<=n;u++){LL l,r;scanf("%llu%llu",&l,&r);sum[l]^=f[u];sum[r+1]^=f[u];g[r]^=f[u];h[l]^=f[u];sum1[l]^=f1[u];sum1[r+1]^=f1[u];g1[r]^=f1[u];h1[l]^=f1[u];cnt[l]++;cnt[r+1]--;}for (LL u=1;u<=m;u++) h[u]=h[u]^h[u-1];for (LL u=m;u>=1;u--) g[u]=g[u]^g[u+1];for (LL u=0;u<=m;u++) g[u]=g[u+1];for (LL u=1;u<=m;u++) sum[u]=sum[u]^sum[u-1];for (LL u=1;u<=m;u++) sum[u]=sum[u]^sum[u-1];for (LL u=1;u<=m;u++) h1[u]=h1[u]^h1[u-1];for (LL u=m;u>=1;u--) g1[u]=g1[u]^g1[u+1];for (LL u=0;u<=m;u++) g1[u]=g1[u+1];for (LL u=1;u<=m;u++) sum1[u]=sum1[u]^sum1[u-1];for (LL u=1;u<=m;u++) sum1[u]=sum1[u]^sum1[u-1];LL ans=0;mp[g[0]^sum[0]^g1[0]^sum1[0]]=1;mp1[g[0]^sum[0]^g1[0]^sum1[0]]=0;for (LL u=1;u<=m;u++){LL xx=(h[u]^tot^sum[u]^h1[u]^sum1[u]);ans=ans+mp[xx]*u-mp1[xx];mp[g[u]^sum[u]^g1[u]^sum1[u]]++;mp1[g[u]^sum[u]^g1[u]^sum1[u]]+=u;}/*for (LL i=1;i<=m;i++)for (LL u=0;u<i;u++)if ((g[u]^h[i]^tot^(sum[i]^sum[u]))==0)ans=ans+(i-u);*/for (LL u=1;u<=m;u++) cnt[u]=cnt[u-1]+cnt[u];for (LL u=1;u<=m;u++) cnt[u]=cnt[u-1]+cnt[u];/*for (LL u=1;u<=m;u++) printf("%llu ",cnt[u]);printf("\n");*/LL r=0;for (LL l=0;l<m;l++){r=max(r,l);while (r<=m&&cnt[r]==cnt[l]) r++;r--;    ans=ans-calc(r-l);}printf("%llu\n",ans);return 0;
}