自动搬运

查看原文

来自洛谷，原作者为

	Seauy I remember your song, sung by centuries of wind.

搬运于2025-08-24 22:12:29，当前版本为作者最后更新于2025-01-27 15:36:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先把两个集合的并的大小换成两个集合大小之和减交的大小，问题变成如何快速查询两个集合的交。我们有两种暴力，一种是直接做集合的交，另一种是从元素对查询的贡献入手，维护拥有某个元素的集合的集合，维护一张 $m\times m$ 的表直接表示答案，每次加入新的集合暴力扫一遍之前已经加入的集合更新答案。

第一种暴力可以用 bitset 优化，第二种暴力，设最终拥有元素 $i$ 的集合有 $s_i$ 个，则要更新答案

次。考虑对两种暴力根号分治平衡复杂度，对 $s_i\leq S$ 的元素做第二种暴力，对剩下的 $O(\frac{m}{S})$ 个元素做第一种暴力。暴力一的复杂度为 $O(\frac{m^2}{Sw})$，暴力二的复杂度为 $O(mS)$，取 $S=\sqrt{\frac{m}{w}}$ 可得到最优复杂度 $O(m\sqrt{\frac{m}{w}})$。

然后还有些问题，首先 bitset 开太多空间要炸（没有炸太多），但是由于所有 bitset 中为 $1$ 的位置总共不超过 $m$ 个，所以考虑当有至少两个元素的时候再开辟 bitset 的内存，这样空间可以减半；最后是关于 $m\times m$ 的表如何维护，直接上哈希表常数会爆炸，但我们可以离线处理，把每次修改看成一个二元组 $(a,b)$，查询拆成 $(x_1,x_2),(x_2,x_1)$（$x_1=x_2$ 时特判），表示查已经插入的二元组中有多少个跟我一样。对于第一维的每种取值都开个链表，按时间顺序将修改跟查询插入，统计贡献时开个桶处理第二维就好了。由于要存下所有修改，空间也是 $O(m\sqrt{\frac{m}{w}})$ 的。

如果被卡常记得调一调块长。下面给个参考代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM=1e6,S=100,B=(MAXM-1)/(S+1)+1,SIZE=MAXM*S/2+2*MAXM;

int Read()
{
	int res=0;char c;
	while(!isdigit(c=getchar()));
	while(isdigit(c)) res=res*10+c-'0',c=getchar();
	return res;
}
void Print(int x)
{
	if(x<10) {putchar('0'+x);return;}
	int y=x/10;
	Print(y);
	putchar('0'+x-y*10);
}

int m,opt[MAXM+5],X[MAXM+5],Y[MAXM+5];
bitset<B> Set[MAXM/2+5];
int SID[MAXM+5],Single[MAXM+5],snum;
vector<int> Q[MAXM+5];
int buc[MAXM+5],Code[MAXM+5],tot;
int cnt[MAXM+5];
int ans[MAXM+5],qry[SIZE+5],lst[MAXM+5]; 

int Cap(int a,int b)
{
	if(!SID[a] || !SID[b]) return 0;
	if(SID[a]>0 && SID[b]>0) return (Set[SID[a]]&Set[SID[b]]).count();
	if(SID[a]>0) return Set[SID[a]][Single[b]];
	if(SID[b]>0) return Set[SID[b]][Single[a]];
	return Single[a]==Single[b];
}

int main()
{
	m=Read();
	for(int i=1;i<=m;i++)
	{
		opt[i]=Read(),X[i]=Read(),Y[i]=Read();
		if(opt[i]==1) ++buc[Y[i]];
	}
	for(int i=1;i<=m;i++) if(buc[i]>S) Code[i]=tot++;
	for(int i=1;i<=m;i++)
		if(opt[i]==1) {if(buc[Y[i]]<=S) lst[X[i]]+=cnt[Y[i]]++;}
		else if(X[i]!=Y[i]) ++lst[X[i]],++lst[Y[i]];
	for(int i=1;i<=m;i++) lst[i]+=lst[i-1];
	for(int i=m;i;i--) cnt[i]=0,lst[i]=lst[i-1];
	for(int i=1;i<=m;i++)
		if(opt[i]==1)
		{
			++cnt[X[i]];
			if(buc[Y[i]]<=S)
			{
				for(int j=0;j<Q[Y[i]].size();j++) qry[++lst[X[i]]]=Q[Y[i]][j];
				Q[Y[i]].push_back(X[i]);
			}
			else
			{
				if(!SID[X[i]]) {Single[X[i]]=Code[Y[i]],SID[X[i]]=-1;continue;}
				if(SID[X[i]]<0) Set[SID[X[i]]=++snum][Single[X[i]]]=1;
				Set[SID[X[i]]][Code[Y[i]]]=1;
			}
		}
		else
		{
			if(X[i]==Y[i]) {ans[i]=cnt[X[i]];continue;}
			ans[i]=cnt[X[i]]+cnt[Y[i]]-Cap(X[i],Y[i]);
			qry[++lst[X[i]]]=qry[++lst[Y[i]]]=-i;
		}
	for(int i=1;i<=m;i++) cnt[i]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=lst[i-1]+1;j<=lst[i];j++)
			if(qry[j]>0) ++cnt[qry[j]];
			else
			{
				int v=-qry[j];
				if(i==X[v]) ans[v]-=cnt[Y[v]];
				else ans[v]-=cnt[X[v]];
			}
		for(int j=lst[i-1]+1;j<=lst[i];j++) if(qry[j]>0) --cnt[qry[j]];
	}
	for(int i=1;i<=m;i++) if(opt[i]==2) Print(ans[i]),putchar('\n');
	return 0;
}