洛谷题面

首黑祭，这道题思维难度紫，但是代码难度黑。。。

调了一上午，足足三个小时。

题目大意

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为 \(n\) 行 \(n\) 列的网格图，其中每个格子要么是空的，要么有障碍物。行从上到下依次被编号为 \(1\) 到 \(n\)，列从左到右依次被编号为 \(1\) 到 \(n\)。

存放飞机零件的大型集装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐标轴的正方形。对于一个奇数 \(k\)，一个尺寸为 \(k\) 的集装箱是一个包含 \(k\) 行 \(k\) 列的正方形。一个集装箱的坐标为其中心格子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。

给定 \(q\) 对格子 \(A_k\) 和 \(B_k\)，对于每对格子，请找到能从 \(A_k\) 移动到 \(B_k\) 的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。

前置知识

• \(\rm Kruskal\) 重构树。

从下面的例子入手：

该例最小生成树为：

我们按照 \(\rm Kruskal\) 的方式建树，设要连接的边为 \((u,v)\)，通过并查集可求得 \(u\) 的祖先节点为 \(x\)，\(v\) 的祖先节点为 \(y\)。

若 \(x\neq y\)，则新建一个节点 \(z\) 作为 \(x,y\) 的父亲来合并 \(x,y\)，\(z\) 的点权为边 \((x,y)\) 的长度。

最后我们建出来了一棵二叉树，具体长这样：

这棵树拥有以下性质：

• 叶子节点都是构成最小生成树的节点。

• 生成树中有 \(n\) 个节点，会产生 \(n-1\) 个含有点权的节点，共 \(n+n-1=2\cdot n-1\) 个节点。

• 按最小生成树重构的重构树是大根堆，按最大生成树重构的重构树是小根堆。

• 按最小生成树重构的重构树中任意两点 \(a,b\) 的路径中的最大边权为它们 \(\operatorname{LCA}(a,b)\) 的点权，也是 \(a,b\) 路径中最大边权的最小值，按最大生成树重构的重构树中任意两点 \(a,b\) 的路径中的最小边权为它们 \(\operatorname{LCA}(a,b)\) 的点权，也是 \(a,b\) 路径中最小边权的最大值。

模板代码：

namespace ex_Kruskal{
	// 注意数组开两倍! 
	
	int nowidx,idx;
	inline bool cmp1(Node x,Node y) { // 按最小生成树重构的重构树
		return x.w < y.w;
	}
	inline bool cmp2(Node x,Node y) { // 按最大生成树重构的重构树
		return x.w > y.w;
	}
	inline void add(int u,int v) {
		gra[++ idx].v = v,gra[idx].nxt = head[u];
		head[u] = idx;
	}
	
	inline void Kruskal() {
		for (register int i = 1;i <= n * 2 - 1; ++ i) {
			fa[i] = i;
		}
		sort (node + 1,node + m + 1,ex_Kruskal::cmp);
		
		nowidx = n;
		for (register int i = 1;i <= m; ++ i) {
			int x = getf(node[i].u),y = getf(node[i].v);
			if (x != y) {
				val[++ nowidx] = node[i].w;//存储当前节点的点权
				fa[x] = fa[y] = nowidx;
				
				add(nowidx,x),add(nowidx,y);
			}
		}
	}
}

题目分析

首先来考虑一下思路。

求出每个坐标能放置的最大正方形边长，并令其为该个坐标的点权，每次询问转换为求出两点路径上最小点权的最大值，注意到“最小/最大”，考虑 \(\rm Kruskal\) 重构树。

对于每个坐标，都对它相邻的坐标连边，但是直接连边空间爆炸，所以每个坐标，点权相同且相邻的缩为一个点。再连边即可。我们连出来了一棵树（可能是森林！！！因为如果周围是障碍物的话不会连边），重构树即可。

怎么求每个坐标能放置的最大正方形边长呢？我们先 \(\mathcal{O(n^2)}\) 求出每个矩阵的障碍物数量。如果一个坐标不是障碍物，那么二分从正方形中心点到正方形边界的距离，因为是奇数这样好算，再看看这个正方形内有没有障碍物就 \(\mathbf{ok}\) 了。

代码

//2022/2/18
//2022/2/19
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include //need "INT_MAX","INT_MIN"
#include //need "memset"
#include 
#include 
#include 
#define enter() putchar(10)
#define debug(c,que) cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) cout << arr[i] << w;
#define speed_up() cin.tie(0),cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define Abs(x) ((x) > 0 ? (x) : (-x))
const int mod = 1e9 + 7;
inline int MOD(int x) {
	while (x < 0) x += mod;
	while (x >= mod) x -= mod;
	return x;
}
namespace Newstd {
	char buf[1 << 21],*p1 = buf,*p2 = buf;
	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
	}
	inline int read() {
		int ret = 0,f = 0;char ch = getc();
		while (!isdigit(ch)) {
			if(ch == '-') f = 1;
			ch = getc();
		}
		while (isdigit(ch)) {
			ret = (ret << 3) + (ret << 1) + ch - 48;
			ch = getc();
		}
		return f ? -ret : ret;
	}
	inline void write(int x) {
		if(x < 0) {
			putchar('-');
			x = -x;
		}
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}
using namespace Newstd;
using namespace std;
typedef pair PII;

const short dx[] = {0,0,-1,1};
const short dy[] = {1,-1,0,0};
const int INF = 0x3f3f3f3f;
const int ma = 1005;
int fa[ma * ma],dep[ma * ma],fath[ma * ma],du[ma * ma],head[ma * ma],val[ma * ma],sum[ma][ma],maxsiz[ma][ma],bel[ma][ma],f[ma * ma][21];// 每个点的最大矩形
bool vis[ma][ma];
char mp[ma][ma];
int n,m,cnt,idx,num,nowidx;
struct Node {
	int u,v,w;
} node[(ma * ma) << 1];
struct Gragh {
	int v,nxt;
} gra[(ma * ma) << 1];
inline bool check(int i,int j,int len) {
	if (i - len < 1 || i + len > n || j - len < 1 || j + len > n) return false;
	if (sum[i + len][j + len] - sum[i - len - 1][j + len] - sum[i + len][j - len - 1] + sum[i - len - 1][j - len - 1] == 0){
		return true;
	}
	return false;
}
inline int getsiz(int i,int j) {
	int l = 0,r = n / 2,ans;
	while (l <= r) {
		int mid = l + r >> 1;// 二分矩阵中心点到边界的距离
		if (check(i,j,mid)) {
			l = mid + 1;
			ans = mid;
		} else {
			r = mid - 1;
		}
	}
	return ans * 2 + 1;
}
inline void bfs(int i,int j,int belong) {
	queueq;
	vis[i][j] = true,bel[i][j] = belong;
	q.push({i,j});
	while (!q.empty()) {
		PII u = q.front();q.pop();
		int x = u.first,y = u.second;
		for (register int k = 0;k < 4; ++ k) {
			int nx = x + dx[k],ny = y + dy[k];
			if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && maxsiz[nx][ny] == maxsiz[x][y] && vis[nx][ny] == false) {
				vis[nx][ny] = true,bel[nx][ny] = belong;
				q.push({nx,ny});
			}
		}
	}
}
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
inline void merge(int x,int y) {
	int f1 = getf(x),f2 = getf(y);
	if (f1 != f2) fa[f1] = f2;
}
inline void ADD(int u,int v,int w) {
	node[++ idx].u = u,node[idx].v = v,node[idx].w = w;
}
inline void add(int u,int v) {
	gra[++ num].v = v,gra[num].nxt = head[u],head[u] = num;
}
namespace ex_Kruskal {
	inline bool cmp(Node x,Node y) {
		return x.w > y.w;
	}
	inline int getfath(int x) {
		return fath[x] == x ? x : fath[x] = getfath(fath[x]);
	}
	inline void Kruskal() {
		nowidx = cnt;
		for (register int i = 1;i <= n * n; ++ i) {
			fath[i] = i;
		}
		for (register int i = 1;i <= idx; ++ i) {
			int x = getfath(node[i].u),y = getfath(node[i].v);
			if (x != y) {
				val[++ nowidx] = node[i].w;
				du[x] ++,du[y] ++;
				fath[x] = fath[y] = nowidx;
				add(nowidx,x),add(nowidx,y);
			}
		}
	}
}
inline void dfs(int now,int dad,int depth) {
	dep[now] = depth,f[now][0] = dad;
	for (register int i = 1;i <= 20; ++ i) {
		f[now][i] = f[f[now][i - 1]][i - 1];
	}
	for (register int i = head[now];i;i = gra[i].nxt) {
		int v = gra[i].v;
		if (v != dad) {
			dfs(v,now,depth + 1);
		}
	}
}
inline int LCA(int x,int y) {
	if (dep[x] < dep[y]) swap(x,y);
	for (register int i = 20;i >= 0; -- i) {
		if (dep[f[x][i]] >= dep[y]) {
			x = f[x][i];
		}
	}
	if (x == y) return x;
	for (register int i = 20;i >= 0; -- i) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i],y = f[y][i];
		}
	}
	return f[x][0];
}
int main(void) {
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	mst(val,0x3f);
	scanf("%d",&n);
	for (register int i = 1;i <= n; ++ i) {
		scanf("%s",mp[i] + 1);
	}
	for (register int i = 1;i <= n; ++ i) {
		for (register int j = 1;j <= n; ++ j) {
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
			if (mp[i][j] == '#') sum[i][j] ++;//有障碍物
		}
	}
	for (register int i = 1;i <= n; ++ i) {
		for (register int j = 1;j <= n; ++ j) {
			if (mp[i][j] == '.') {
				maxsiz[i][j] = getsiz(i,j);
			} else {
				maxsiz[i][j] = -1;
			}
		}
	}
	for (register int i = 1;i <= n; ++ i) {
		for (register int j = 1;j <= n; ++ j) {
			if (vis[i][j] == false && mp[i][j] == '.') {
				bfs(i,j,++ cnt);
			}
		}
	}
	for (register int i = 1;i <= n * n; ++ i) fa[i] = i;
	for (register int i = 1;i <= n; ++ i) {
		for (register int j = 1;j <= n; ++ j) {
			if (mp[i][j] == '.') {
				for (register int k = 0;k < 4; ++ k) {
					int nx = i + dx[k],ny = j + dy[k];
					if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && bel[i][j] != bel[nx][ny] && mp[nx][ny] == '.' && getf(bel[i][j]) != getf(bel[nx][ny])) {
						ADD(bel[i][j],bel[nx][ny],min(maxsiz[i][j],maxsiz[nx][ny])),ADD(bel[nx][ny],bel[i][j],min(maxsiz[i][j],maxsiz[nx][ny]));
						merge(bel[i][j],bel[nx][ny]);
					}
				}
			}
		}
	}
	sort(node + 1,node + idx + 1,ex_Kruskal::cmp);
	ex_Kruskal::Kruskal();
	for (register int i = 1;i <= nowidx; ++ i) {
		if (!du[i]) {
			dfs(i,0,1);
		}
	}
	m = read();
	while (m --) {
		int x1 = read(),y1 = read(),x2 = read(),y2 = read();
		if (bel[x1][y1] == bel[x2][y2]) {
			printf("%d\n",maxsiz[x1][y1]);
		} else if (ex_Kruskal::getfath(bel[x1][y1]) != ex_Kruskal::getfath(bel[x2][y2])) {
			puts("0");
		} else {
			int lca = LCA(bel[x1][y1],bel[x2][y2]);
			if (val[lca] == INF) puts("0");
			else printf("%d\n",val[lca]);
		}
	}

	return 0;
}