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

更差的阅读体验

---

并集不好做，转化为求交。

当 \(n\) 比较小的时候，我们会一个 \(O(\frac{n^2}{\omega})\) 的 bitset 做法。

当一个数字被插入的次数很小的时候，我们在加入这个数字的时候，可以直接枚举这个数字出现的位置，将这两个集合的交集 \(+1\)。

这启发我们根号分治。设置阈值 \(B\)，对于出现次数 \(< B\) 的数字，我们枚举这个数字出现的位置，然后更新交集，这部分复杂度 \(O(B)\)。对于出现次数 \(\ge B\) 的数字，我们使用 bitset 可以做到 \(O(\frac{n}{B\omega})\)。

取 \(B = \sqrt \frac{n}{\omega}\) 可以做到 \(O(n\sqrt \frac{n}{\omega})\)，实现中因为 bitset 比较快，可以稍微把阈值调小一点，我使用了 \(80\)。

然后会被卡常和卡空间。我们可以对哈希表和 bitset 动态开点，然后把很慢很慢的 vector 换成链表，这样就很快。最慢点 572 毫秒。

然后这道题就做完了，复杂度 \(O(n\sqrt \frac{n}{\omega})\)。

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define N 1000006
#define K 12506
using namespace std;
constexpr int M_X = 1 << 20;

char buf[M_X], *p1, *p2;

inline char gc() {
  if (p1 == p2) {
    p1 = buf;
    p2 = p1 + fread(buf, 1, M_X, stdin);
  }
  return p1 == p2 ? EOF : *p1++;
}
inline int read()
{
	int ret=0,f=0; char ch=gc();
	while((ch<'0'||ch>'9')&&ch!='-')ch=gc();
	if(ch=='-')f=1,ch=gc();
	while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=gc();
	return f?-ret:ret;
}
inline void write(int k)
{
	if(k<0)putchar('-'),k=-k;
	static int nnum[20],ttp=0;
	while(k)nnum[++ttp]=k%10,k/=10;
	if(!ttp)nnum[++ttp]=0;
	while(ttp)putchar(nnum[ttp--]^48);
}
using ull=unsigned long long;
constexpr int B=80;
constexpr ull P=1e9+1011;
int q,occ[N],sz[N],b[N],vis[N],bn;
struct Ask {int opt,x,y;} ask[N];
bitset<K> *bt[N];
inline ull has(int x,int y){return P*x+y;}
__gnu_pbds::gp_hash_table<int,int> *mp[N];
int tot,head[N],val[N],nxt[N];
main()
{
	q=read();
	for(int i=1;i<=q;i++)
	{
		ask[i]={read(),read(),read()};
		if(ask[i].opt==1)occ[ask[i].y]++;
		else if(ask[i].x>ask[i].y)swap(ask[i].x,ask[i].y);
		if(ask[i].opt==2)
		{
			if(!mp[ask[i].x])mp[ask[i].x]=new __gnu_pbds::gp_hash_table<int,int> ();
			(*mp[ask[i].x])[ask[i].y]=0;
		}
	}
	for(int i=1;i<=q;i++)if(occ[i]>B)b[++bn]=i;
	for(int i=1;i<=q;i++)if(ask[i].opt==1)
	{
		int x=ask[i].x,y=ask[i].y;
		if(occ[ask[i].y]>B)
		{
			int t=lower_bound(b+1,b+1+bn,y)-b;
			if(!bt[x])bt[x]=new bitset<K> ();
			bt[ask[i].x]->set(t);
		} else {
			for(int i=head[y];i;i=nxt[i])
			{
				int l=min(val[i],x),r=max(val[i],x);
				if(mp[l]&&mp[l]->find(r)!=mp[l]->end())(*mp[l])[r]++;
			}
			val[++tot]=x,nxt[tot]=head[y],head[y]=tot;
		}
		sz[x]++;
	} else {
		int x=ask[i].x,y=ask[i].y; if(x==y){write(sz[x]),putchar(10); continue;}
		int ans=sz[x]+sz[y]-(*mp[x])[y];
		if(bt[x]&&bt[y])ans-=(*bt[x]&*bt[y]).count();
		write(ans),putchar(10);
	}
	return 0;
}