推结论：Gym - 103371I

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135208880

https://vj.imken.moe/contest/600552#problem/A

对上下做一次，对左右做一次，求出 xix_i 表示高度为 ii 时宽度最大为 xix_i ， yjy_j 表示宽度为 jj 时高度最大为 yjy_j ，然后丢坐标系上求交即可：

在这里插入图片描述

考虑证明。必要性显然。充分性我们可以对所有矩形在合法位置放，而由于限制的存在所以必然不会有一个地方“卡着”，因为边界太窄而放不下。（还是要感性理解）

1
2
3
4
st coding at 16:16
st bugging at 16:36
fn bugging at 20:49
fn blogging at 20:58
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 3010
//#define M
//#define mo
void Mn(int &a, int b) { a = min(a, b); }
int n, m, i, j, k, T;
char str[N][N], str2[N][N]; 
int U[N][N], L[N][N], R[N][N], a[N], a1[N], a2[N], b[N], b1[N], b2[N]; 
int ans; 

void work(int n, int m, int *a, char (*str)[N]) {
	memset(U, 0, sizeof(U)); 
	memset(L, 0, sizeof(L)); 
	memset(R, 0, sizeof(R)); 
	for(i=1; i<=n; ++i) debug("%s\n", str[i]+1); 
	for(i=1; i<=n; ++i) a[i]=1e9; 
	for(i=n; i>=1; --i) {
		for(j=1; j<=m; ++j) {
			if(str[i][j]=='#') U[i][j]=0, L[i][j]=0; 
			else U[i][j]=U[i+1][j]+1, L[i][j]=L[i][j-1]+1; 
			if(U[i][j] && (str[i-1][j]=='#' || i==1)) a[U[i][j]+1]=0; 
		}
		for(j=m; j>=1; --j) {
			if(str[i][j]=='#') R[i][j]=0; 
			else R[i][j]=R[i][j+1]+1; 
		}
		for(j=1; j<=m; ++j) if(U[i][j] > 1) Mn(L[i][j], L[i+1][j]), Mn(R[i][j], R[i+1][j]); 
		for(j=1; j<=m; ++j) if(U[i][j]) Mn(a[U[i][j]], R[i][j]+L[i][j]-1), debug("[%lld %lld][%lld] %lld\n", i, j, U[i][j], R[i][j]+L[i][j]-1); 
	}
	debug("U:\n"); for(i=1; i<=n; ++i, debug("\n")) for(j=1; j<=m; ++j) debug("%d", U[i][j]); 
	debug("L:\n"); for(i=1; i<=n; ++i, debug("\n")) for(j=1; j<=m; ++j) debug("%d", L[i][j]); 
	debug("R:\n"); for(i=1; i<=n; ++i, debug("\n")) for(j=1; j<=m; ++j) debug("%d", R[i][j]); 
	for(i=2; i<=n; ++i) a[i] = min(a[i], a[i-1]); 
	for(i=1; i<=n; ++i) debug("%d ", a[i]); debug("\n"); 
	debug("----------\n"); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) scanf("%s", str[i]+1); 
	for(i=1; i<=n; ++i) {
		for(j=1; j<=m; ++j) if(str[i][j]!='#') break; 
		if(j<=m) break; 
	}
	if(i>n) return printf("0"), 0; 
	work(n, m, a1, str); 
	for(i=1; i<=n-i+1; ++i) 
		for(j=1; j<=m; ++j) swap(str[i][j], str[n-i+1][j]); 
	work(n, m, a2, str); 
	for(i=1; i<=n-i+1; ++i) 
		for(j=1; j<=m; ++j) swap(str[i][j], str[n-i+1][j]); 
	for(i=1; i<=n; ++i) for(j=1; j<=m; ++j)
	 	str2[j][n-i+1] = str[i][j]; 
	work(m, n, b1, str2); 
	for(i=1; i<=m-i+1; ++i) for(j=1; j<=n; ++j) swap(str2[i][j], str2[m-i+1][j]); 
	work(m, n, b2, str2); 
	for(i=1; i<=n; ++i) a[i]=min(a1[i], a2[i]); 
	for(i=1; i<=m; ++i) b[i]=min(b1[i], b2[i]); 
	for(i=1; i<=n; ++i) debug("%d ", a[i]); debug("\n"); 
	for(i=1; i<=m; ++i) debug("%d ", b[i]); debug("\n"); 
	for(i=1, j=m; i<=n; ++i) {
		while(j && b[j] < i) --j; 
		ans += min(a[i], j); 
	}
	printf("%d", ans); 
	return 0;
}