专栏文章

题解：P5607 [Ynoi2013] 无力回天 NOI2017

EEterna
P5607题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mined6cu
此快照首次捕获于
2025/12/02 01:02
3 个月前
此快照最后确认于
2025/12/02 01:02
3 个月前
查看原文
简单题。
首先 ∣S∪T∣=∣S∣+∣T∣−∣S∩T∣| S\cup T| = |S|+|T|-|S\cap T|。考虑求 ∣S∩T∣|S\cap T| 即可。
对于每种颜色的出现次数阈值分治，设阈值为 BB。
对于出现次数 ≥B\ge B 的颜色，只有 O(n/B)\mathcal{O}(n/B) 个，开个 bitset 跑暴力即可做到 O(n/Bw)\mathcal{O}(n/Bw)。
对于出现次数 <B<B 的颜色，考虑到有 O(B2)\mathcal{O}(B^2) 个询问点对包含它。枚举这些点对，所有颜色共有 O(nB)\mathcal{O}(nB) 个，做单点加即可。
然后由于只有 O(n)\mathcal{O}(n) 次询问，我们只需加到有询问的点对上，这样第二部分的空间是线性的。
取 B=n/wB=\sqrt{n/w}，时空复杂度均为 O(nn/w)\mathcal{O}(n\sqrt{n/w})。
然而空间不太够用。
第一部分将这些次数 ≥B\ge B 的颜色每 KK 一组处理。空间复杂度变为 O(nK/w)\mathcal{O}(nK/w)，时间复杂度加上 O(n2/BK)\mathcal{O}(n^2/BK)。
取 K=wK=w，空间变为线性，时间复杂度仍为 O(nn/w)\mathcal{O}(n\sqrt{n/w})。
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 400000, stdin), pa == pb) ? EOF : *pa++
#define gt(x,y) (1ull*x*n+y)
using namespace std;
static char buf[400000], * pa(buf), * pb(buf);
inline int read()
{
	unsigned int x=0,s=gc;while(s<48)s=gc;
	while(s>=48)x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
const int N=1000001,K=64,B=40;
int n,siz[N],sz[N],ans[N],d[N],t[N];ull b[N];
basic_string<int> v,P[N];unordered_map<ull,int> mp;
struct qu{int op,x,y;}q[N];
inline void sol()
{
	for(int i=1;i<=n;++i)
	{
		if(q[i].op==1&&~d[q[i].y])b[q[i].x]|=(1ull<<d[q[i].y]);
		if(q[i].op==2&&(b[q[i].x]|b[q[i].y]))ans[i]+=__builtin_popcountll(b[q[i].x]|b[q[i].y]);
	}
	for(int i=1;i<=n;++i)b[i]=0;for(int i:v)d[i]=-1;v.clear();
}
signed main()
{
	n=rd,memset(d,-1,sizeof(d));
	for(int i=1;i<=n;++i)q[i]={rd,rd,rd},siz[q[i].y]+=(q[i].op==1);
	for(int i=1;i<=n;++i)
	{
		if(q[i].op==2)mp[gt(q[i].x,q[i].y)]=mp[gt(q[i].y,q[i].x)]=i;
		if(siz[i]>=B)d[i]=v.size(),v.push_back(i);if(v.size()==K)sol();
	}
	if(v.size())sol();
	for(int i=1;i<=n;++i)
	{
		auto [op,x,y]=q[i];
		if(op==1&&siz[y]<B){P[y].push_back(x);for(int j:P[y])if(mp.count(gt(x,j)))++t[mp[gt(x,j)]];++sz[x];}
		if(op==2){ans[i]+=sz[x]+sz[y];if(sz[x]&&sz[y])ans[i]-=t[mp[gt(x,y)]];}
	}
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(int i=1;i<=n;++i)if(q[i].op==2)cout<<ans[i]<<'\n';return 0;
}

评论

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

正在加载评论...