「USACO 2021.1 Platinum」Paint by Letters

Posted on Edited on In

「USACO 2021.1 Platinum」Paint by Letters

统计连通块问题，暴力是 \(O(qn^2)\) ，而且常数大

容易想到 平面图的欧拉定理 优化

下文和代码中， \(V,E,F\) 分别为点集，边集，区域集合

其中 \(|V|\) 可以直接得到， \(|E|\) 可以 \(O(n^2)\) 前缀和预处理出来， \(O(1)\) 查询

下面处理区域个数

Solution1

前缀和所有大小为1（即被四个点包住的）区域，暴力预处理所有大小 \(>1\) 的区域，个数为 \(O(\frac{nm}{4})\)

然后可以转化为一个对于给定矩形查询包含的 矩形个数 的问题

实际上这个题目 \(q\) 小直接枚举就是了。。

复杂度为 \(O(nm+q\frac{nm}{4})\) ，足够通过时限

写的够丑可以得到这个代码

矩形区间查询问题 ，不知道有没有什么更好的方法

ps:垃圾数据没有卡，因此实际上数据中的空白块数量非常少，预处理写得稍微好一点可能还比下面的做法常数小

\[ \ \]

Solution2

用 \((x,y)\) 表示 \((x,y),(x+1,y),(x,y+1),(x+1,y+1)\) 中间的一个空白区域

这些空白块会被染色块之间的边隔开，但是依然可以形成四联通块

预处理出所有空白区域的连通块，每个连通块选取一个代表点 \(S_i\)

我们要统计一个区域中的空白连通块个数，注意到

跨出区域范围的空白点，并不是断开了，而是和最外层的无穷空白区合并在一起

因此可以先求出在区域中存在的连通块个数，然后将连通到区域外的部分去掉

具体实现上：

前缀和预处理出 \(S_i\) 的位置，每次查询区域中的 \(S_i\) 个数（这样的统计不完全）

然后将 \(S_i\) 在区域中，且跨出区域的白色连通块删掉即可

跨出部分枚举四条边界即可

每次查询枚举边界，因此复杂度为 \(O(nm+q(n+m))\)

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>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=1e3+10,INF=1e9+10;
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

int n,m,q;
char A[N][N];
int vis[N*N],I[N][N],E[4][N][N],S[N][N];
// B,C预处理上/左边个数
int B[N][N],C[N][N];
int X[N*N],Y[N*N],cnt;
// 搜索空白连通块
void dfs(int x,int y){
	I[x][y]=cnt;
	rep(i,0,3) if(E[x][y][i]) {
		int x1=x+dx[i],y1=y+dy[i];
		if(!x1 || !y1||x1>=n || y1>=m || I[x1][y1]) continue;
		dfs(x1,y1);
	}
}
int Sum(const int A[N][N],int x1,int y1,int x2,int y2){
	x1--,y1--;
	return A[x2][y2]-A[x1][y2]-A[x2][y1]+A[x1][y1];
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	rep(i,1,n) scanf("%s",A[i]+1);
	rep(i,1,n) rep(j,1,m) {
		E[0][i][j-1]=E[1][i][j]=A[i][j]!=A[i+1][j];
		E[2][i-1][j]=E[3][i][j]=A[i][j]!=A[i][j+1];
        // 处理一下空白点之间的边
		if(A[i-1][j]==A[i][j]) B[i][j]++;
		if(A[i][j]==A[i][j-1]) C[i][j]++;
	}
    // 预处理空白点之间的集合
	rep(i,1,n-1) rep(j,1,m-1) if(!I[i][j]) {
		X[++cnt]=i,Y[cnt]=j,vis[cnt]=q+1;
		dfs(i,j),S[i][j]++;
	}
	rep(i,1,n) rep(j,1,m) {
		B[i][j]+=B[i-1][j]+B[i][j-1]-B[i-1][j-1];
		C[i][j]+=C[i-1][j]+C[i][j-1]-C[i-1][j-1];
		S[i][j]+=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
	}
	while(q--) {
		int lx,ly,rx,ry; scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
		int V=(rx-lx+1)*(ry-ly+1);
		int E=Sum(B,lx+1,ly,rx,ry)+Sum(C,lx,ly+1,rx,ry);
		int F=Sum(S,lx,ly,rx-1,ry-1);
		auto Check=[&](int i){ if(vis[i]!=q && lx<=X[i] && X[i]<rx && ly<=Y[i] && Y[i]<ry) vis[i]=q,F--; };
		rep(i,lx,rx-1) {
			if(::E[0][i][ry-1]) Check(I[i][ry-1]);
			if(::E[1][i][ly]) Check(I[i][ly]);
		}
		rep(i,ly,ry-1) {
			if(::E[2][rx-1][i]) Check(I[rx-1][i]);
			if(::E[3][lx][i]) Check(I[lx][i]);
		}
		printf("%d\n",V-E+F);
	}
}