你说得对，但是这是哪门子的 3500

· · 题解

幽默远古 3500。

思淺路析：

考虑对 r 扫描线，判断一个 l 合法即是对于 n 个序列的 [l,r] 问是否全部为奇数个 1 或为 0。

看到判断出现次数的奇偶性，立马想到异或哈希，由于出现次数是奇数和没有出现这两个条件在异或下是相反的，考虑将出现次数奇数简单地转化为出现次数偶数（即异或和为 0）：

考虑有值区间 [l,r] 的前缀异或和的形式。要求首位为 0，那么就形如 pre_l=0,pre_{l+1}=x,pre_{l+2}=0,...pre_r=[r-l\equiv 1(\bmod 2)]x，即起始位置后移一位即可。相应地，区间 [a,b] 的异或哈希值前缀表示变为 pre_r\oplus pre_l。

由于 n 个序列独立，给每个序列随机一个权值赋上即可，区间赋值打差分标记即可。

去除空区间维护一个指针表示我及之前的最长 n 个序列均无赋值的长度，减掉这一段的贡献即可。

视哈希表复杂度 O(1)，则时间复杂度 O(n+m)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define un unsigned 
using namespace std;
ll n,m;
random_device my;
mt19937_64 rd(my());
un ll pre[200005],af[200005];
ll cot[200005],cnt[200005];
unordered_map<un ll,pair<ll,ll>>sum;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;++i)
    {
        ll l,r;
        cin>>l>>r;
        un ll val=rd();
        pre[l]^=val;
        af[r]^=val;
        ++cot[l];--cot[r+1];
    }
    un ll res=0;
    for(ll i=1;i<=m;++i)
    {
        cot[i]+=cot[i-1];
        res^=pre[i];
        pre[i]=(pre[i-1]^res^pre[i]);
        res^=af[i];
    }
    ll r=0,ans=0;
    for(ll i=1;i<=m;++i)
    {
        cnt[i]+=cnt[i-1]+cot[i];
        ++sum[pre[i]].first;
        sum[pre[i]].second+=i-1;
        if(cot[i])r=i;
        else while(cnt[i]-cnt[r+1])++r;
        ans+=sum[pre[i]].first*i-sum[pre[i]].second-(i-r)*(i-r+1)/2;
    }
    cout<<ans;
}