P8250 交友问题 题解

发表于 分类于

本文迁移自洛谷原文。

2020年的J组模拟，2022年终于进主题库了

知识点：根号分治

subtask 1：

利用 map 存储，然后暴力。

时间复杂度: $O(n^2\log n)$

subtask 2:

对于每一个节点都开一个 bitset 存储邻接点。(设为 $b_i$ )

查询用 $b_u \ xor \ (b_u \ and \ b_v)$ 即可。$xor$ 为按位异或，$and$ 为按位与。

时间&空间复杂度: $O(\frac{n^2}{\omega})$

subtask 3:

考虑将 subtask 1 和 2 结合起来。

我们设定一个阈值 $limit$。

对于所有度数大于 $limit$ 的节点，我们用 bitset。反之，我们用 map。

$limit$ 大约取在能让大约 $\sqrt{n}$ 个点用 bitset 即可。

查询的时候要分类讨论。（具体见代码）

时间&空间复杂度:$O(n\times\sqrt{\frac{n\log n}{\omega}})$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int n,m,q;
int lim;
vector<int>heavy;
int id[mxn];
vector<bitset<mxn> >T;
map<int,int>have[mxn];
int deg[mxn];
inline void solve(){
	scanf("%d%d%d",&n,&m,&q);
	//cerr<<lim<<'\n';
	for(ri i=1,u,v;i<=m;++i){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
		++deg[u];
		++deg[v];
	}
	sort(deg+1,deg+n+1);reverse(deg+1,deg+n+1);
	lim=deg[min(n,(int)(sqrt(n)*6))];//根号处分治
	memset(id,-1,sizeof(id));
	for(ri i=1;i<=n;++i){
		if(g[i].size()>lim){
			heavy.push_back(i);
			id[i]=heavy.size()-1;bitset<mxn>newb;
			newb&=0;
			for(ri j=0;j<g[i].size();++j)newb[g[i][j]]=1;
			T.push_back(newb);
		}else{
			for(ri j=0;j<g[i].size();++j)have[i][g[i][j]]=1;
		}
	}
	for(ri i=1;i<=q;++i){
		ri u,v;scanf("%d%d",&u,&v);
		if(~id[u] and ~id[v]){  //对两个点是否是重点分类讨论
			bitset<mxn>tmp=T[id[u]]^(T[id[u]]&T[id[v]]);
			tmp[u]=0;tmp[v]=0;
			printf("%d\n",tmp.count());
		}else if(~id[u]){
			ri ans=0;
			for(ri j=0;j<g[v].size();++j)if(g[v][j]==u or g[v][j]==v or T[id[u]][g[v][j]])++ans;
			printf("%d\n",T[id[u]].count()-ans);
		}else if(~id[v]){
			ri ans=0;
			for(ri j=0;j<g[u].size();++j)if(g[u][j]!=u and g[u][j]!=v and !T[id[v]][g[u][j]])++ans;
			printf("%d\n",ans);
		}else{
			ri ans=0;
			for(ri j=0;j<g[u].size();++j)if(g[u][j]!=u and g[u][j]!=v and !have[v][g[u][j]])++ans;
			printf("%d\n",ans);
		}
	}
}
int main(){
	solve();
	return 0;
}