二维分块浅谈

技术分享 6个月前 (09-19) 0 999+

关注

我们以例题探究二维分块的运用以及对分块复杂度的分析，学习如何有效分块

原题链接

题目大意

给定 (n) 个第一象限内的整点 ((x,y))，距离不大于 (r) 的两点间连一条无向边，试求存在奇环的连通块上的所有点。

数据范围

(2leq n leq 10^5 ,1 leq r leq 10^9,0leq x,y leq 5times 10^8)。

解题报告

subtask1：(nleq 10^3)

(O(n^2)) 枚举点对逐条判断建边，然后跑黑白染色即可复杂度 (O(n^2))。

关于黑白染色判断奇环有 2 种方法，分别是 DFS/BFS 直接染色和扩展域并查集（对于一个点 (i) 分别维护两个集合表示同色 (i) 与异色 (i+n)），参见黑白染色方法。

subtask2：(nleq 10^4)

发现边数最多有 (10^8)，直接存图会 MLE，所以我们不存图，在 DFS/BFS 中枚举所有点直接判断是否可达（(1 sim n) 扫一遍）

复杂度 (O(n^2))。

subtask3：(rleq 10)

由于r很小，考虑用 map 将所有点按坐标归类 ((x,y) rightarrow P_1,P_2,cdots)。

这样我们可以把染色时把枚举所有点换成只枚举距离该点 (x) 和 (y) 之差均不超过 (r) 的点，类似一个边长为 (2r) 的正方形.

复杂度 (O(nr^2 log n))。

subtask4：任意两点间距离不小于 (frac{r}{2})

这是很关键的一个 subtask。

点之间距离足够大保证了边数是线性的，可以说边数与点数成正比，边数不多。

可以建图，关键在于如何找出这些边。

这里分块第一是为了方便确定可能连边的范围，第二是为了利用 (frac r2) 的性质。

将平面划分为边长为 (frac{r}{2}) 的正方形格子。将点分配到它们所在的格子中，具体可以用 (map:(idx,idy) rightarrow P_1,P_2,cdots) 来实现 (idx,idy) 均为格子的编号。

对于每个点，考虑所有落在距离它所在格子在 (x,y) 方向上不超过 (r) 的格子上的点，枚举格子并尝试连边，不难发现这是一个以所在格子为中心 (5times 5) 的正方形。

由于每个格子上至多只有 2 个点，所以连边建图的复杂度为 (O(ntimes 2 times 25))。

这是至关重要的一点，只有分块了我们才能以格子为单位快速枚举而不用一个一个坐标枚举，就像分块链表一样可以以格子为单位加快跳转，这是有效的分块。

整体时间复杂度 (O(n)) 或 (O(nlog n))。

subtask5：(y_i=0)

只有一维，具有更多的单调性，不难想到，除了连边除了相邻的点还有跳着连的，跳着连的会形成环。

那么显然如果从一个点开始能够跳过 3 个点，5 个点形成奇环，那么肯定可以跳过 1 个点形成长度为 3 的最小奇环。

所以贪心地只用判断是否存在长度为 3 的奇环即可，这样子就节省了许多不必要的连边。

复杂度 (O(n))。

正解

正解需要充分结合上述 subtask 的思路，最重要的是分块复杂度的分析。

问题的关键就在于减少不必要的连边，这里同样要用到分块的思想。

还是按照 subtask4 的方法分块，不同的是块内可能不止 2 个点了。

我们将点数 (leq 2) 的块称作轻块，点数 (geq 3) 的称作重块。

对于重块，不难发现在同一个块内一定可达，所以重块内一定存在奇环，也就是说重块内的点一定是满足要求的点，因此重块之间可以不需要连边，因为连不连都满足要求。

对于轻块，像先前一样向 (5times 5) 的区域连边，这里有很不可思议的事情发生了，由于重块只可能被距离它不超过r的轻块连到，只有 (5times 5) 的范围。

也就是说重块上的点至多与 (2times 25) 个轻块上的点连边，而轻块上的点也至多与 (2times 25) 个轻块上的点连边，重块之间不连边。

于是乎，复杂度神一般的降到了 (O(n))，下面具体解释一下为什么分块后复杂度就降低了？

最重要的原因是，这种方法免去了重块之间的连边，使得大部分点集中的区域都不需要连边，极大的减少了边数，是有效的。

最难想到的还是复杂度分析，只有你确信这是 (O(n)) 的，才能继续下去，不然只是一个假做法。

具体实现的话，先分块，再枚举每个块。

对于重块，只需直接将块上的点记录答案。

对于轻块，像 subtask4 一样连边。

最后跑一边黑白染色即可。

参考代码

#include <bits/stdc++.h>  #define eb emplace_back #define fi first #define se second using namespace std;  using ll = long long; using PII = pair<int,int>; using vec = vector<int>; const int N=1e5+5;  int n; ll r; struct P{ 	ll x,y; }p[N];  inline ll d(const P &A,const P &B){ 	return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y); }  map<PII,vec> m; vec e[N],V;  struct DSU{ 	int fa[N<<1]; 	void Init(int n){ 		n<<=1; 		for(int i=1;i<=n;i++) fa[i]=i; 	} 	int find(int x){ 		if(x==fa[x]) return x; 		return fa[x]=find(fa[x]); 	} 	void merge(int x,int y){ 		int fx=find(x),fy=find(y); 		if(fx!=fy) fa[fy]=fx;  	} }dsu; int main(){  	ios::sync_with_stdio(false); 	cin.tie(0); cout.tie(0); 	cin>>n>>r; 	double blen=(r+1)/2; 	for(int i=1;i<=n;i++){ 		cin>>p[i].x>>p[i].y; 		m[{(int)(p[i].x/blen),(int)(p[i].y/blen)}].eb(i); 	} 	dsu.Init(n); 	for(auto &[B,V]:m) 		if(V.size()<3){ 			int a=B.fi,b=B.se; 			for(const int &u:V)	 				for(int i=-2;i<=2;i++) 				for(int j=-2;j<=2;j++){ 					int ca=a+i,cb=b+j; 					if(ca<0 or cb<0 or m.find({ca,cb})==m.end() ) continue; 					vec tmp=m[{ca,cb}]; 					for(const int &v:tmp) 						if(u!=v and d(p[u],p[v])<=r*r) 							dsu.merge(u,v+n),dsu.merge(u+n,v); 				} 		}else for(const int &u:V) dsu.merge(u,u+n); 	for(int i=1;i<=n;i++) 		cout<<((dsu.find(i)==dsu.find(i+n)) ?1:0); 	return 0; }