专栏文章

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

NNATO
CF799F题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqns42h
此快照首次捕获于
2025/12/04 07:49
3 个月前
此快照最后确认于
2025/12/04 07:49
3 个月前
查看原文
幽默远古 3500。

思淺路析：

考虑对 rr 扫描线，判断一个 ll 合法即是对于 nn 个序列的 [l,r][l,r] 问是否全部为奇数个 11 或为 00。
看到判断出现次数的奇偶性，立马想到异或哈希，由于出现次数是奇数和没有出现这两个条件在异或下是相反的，考虑将出现次数奇数简单地转化为出现次数偶数（即异或和为 00）：
考虑有值区间 [l,r][l,r] 的前缀异或和的形式。要求首位为 00，那么就形如 prel=0,prel+1=x,prel+2=0,...prer=[r−l≡1( mod 2)]xpre_l=0,pre_{l+1}=x,pre_{l+2}=0,...pre_r=[r-l\equiv 1(\bmod 2)]x，即起始位置后移一位即可。相应地，区间 [a,b][a,b] 的异或哈希值前缀表示变为 prer⊕prelpre_r\oplus pre_l。
由于 nn 个序列独立，给每个序列随机一个权值赋上即可，区间赋值打差分标记即可。
去除空区间维护一个指针表示我及之前的最长 nn 个序列均无赋值的长度，减掉这一段的贡献即可。
视哈希表复杂度 O(1)O(1)，则时间复杂度 O(n+m)O(n+m)。

参考代码：

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...