『并查集』格点统计

本文主要是介绍『并查集』格点统计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们知道，对于$(x1,y1),(x1,y2),(x2,y1)$满足，那么$(x2,y2)$也满足,我们需要通过分析前者和后者的关系来找到规律。即，如何寻求一个方法使得通过前者的标记使得后者被标记到。

我们需要通过对应的$x2$找到对应的$y1$，再从$y1$找到$x1$，$x1$找到$y2$。因此题目就转化成了一个连通性问题。那么，我们就可以对任意$(x,y)$从$x$到$y$连边，再用并查集判断连通性。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <iostream>using namespace std;
const int N = 6000;int n, m, q;
int a[N][N], fa[N];int read(void)
{int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int get(int x) {if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}int main(void)
{freopen("grid.in","r",stdin);freopen("grid.out","w",stdout);n = read(), m = read(), q = read();for (int i=1;i<=n*2;++i) fa[i] = i;while (m --) fa[get(read())] = get(read()+n); for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)a[i][j] = a[i][j-1]+a[i-1][j]-a[i-1][j-1]+(get(i)==get(j+n));while (q --) {int x1 = read(), y1 = read(), x2 = read(), y2 = read();printf("%d\n", a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]);}	return 0;	
} 

这篇关于『并查集』格点统计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---