[COCI2010-2011#2] CRNI(单调栈)

问题分析

首先考虑两个不相交的矩形可能存在的位置关系，我将其分成

1.左右

2.上下

3.左上右下

4.左下右上

发现1,2,3,4之间有相交,考虑四种情况的答案应该是1+2-3-4

统计方法

核心: 统计以一个点作为顶点的矩形数量

以统计$i,j$为右下角的矩形为例，先不考虑矩形大小>1的限制

显然可以在线性时间内处理得到每个$i,j$向上连续延伸的连续1长度，设其为$U_{i,j}$

假设枚举了$i$，从左到右依次扫描$j$，则得到$i,j$位置的答案应该是

$$\begin{aligned} \sum_{k=1}^{j} \min_{d=k}^j\lbrace U_{i,d}\rbrace\end{aligned} $$

这条式子中，相当于枚举了$i,(k,j)$为底，统计向上延伸的最长长度

这个式子可以用单调栈在线性时间内求解，其过程可以描述为

1.每次插入元素$U_{i,j}$，得到它的影响区间$k\in [L,j]$

2.将原先单调栈内$k\in [L,j]$这段区间的答案减掉，改为$U_{i,j}\cdot (j-L+1)$

类似的，可以通过改变循环顺序和额外记录向下延伸的长度$D_{i,j}$来统计四种顶点的答案(详细见代码)

然后可以用前缀和帮助统计以上4种答案，枚举一个端点，另一个查询前缀和即可

tips: 注意累和顺序，前缀和要开long long

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e3+10;

int n;
char a[N][N];
int D[N][N],U[N][N]; //i,j向下/上延伸的最长长度
int stk[N],c[N],top;
int CRR[N][N]; // 以i,j为右下角的矩形个数
int CLL[N][N]; // 以i,j为左上角的矩形个数
int CLR[N][N]; // 以i,j为右上角的矩形个数
int CRL[N][N]; // 以i,j为左下角的矩形个数
ll SLL[N][N],SRL[N][N]; // 前缀和

int main(){
	n=rd();
	rep(i,1,n) scanf("%s",a[i]+1);
	rep(i,1,n) rep(j,1,n) if(a[i][j]=='C') U[i][j]=U[i-1][j]+1;
	drep(i,n,1) rep(j,1,n) if(a[i][j]=='C') D[i][j]=D[i+1][j]+1;
	rep(i,1,n) {
		// 统计四种端点的情况
		top=0;
		int now=0;
		rep(j,1,n) {
			int x=U[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CRR[i][j]=max(now-1,0);
		}

		now=top=0;
		rep(j,1,n) {
			int x=D[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CLR[i][j]=max(now-1,0);
		}

		now=top=0;
		drep(j,n,1) {
			int x=U[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CRL[i][j]=max(now-1,0);
		}

		now=top=0;
		drep(j,n,1) {
			int x=D[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CLL[i][j]=max(now-1,0);
		}
	}

	drep(i,n,1) drep(j,n,1) SLL[i][j]=SLL[i+1][j]+SLL[i][j+1]-SLL[i+1][j+1]+CLL[i][j];
	rep(i,1,n) drep(j,n,1) SRL[i][j]=SRL[i-1][j]+SRL[i][j+1]-SRL[i-1][j+1]+CRL[i][j];
	// 前缀和

	ll ans=0;
	rep(i,1,n) rep(j,1,n) if(CRR[i][j]) ans+=CRR[i][j]*(SLL[i+1][1]+SLL[1][j+1]-SLL[i+1][j+1]);
	rep(i,1,n) rep(j,1,n) ans-=CLR[i][j]*SRL[i-1][j+1];
	// 统计4种情况
	printf("%lld\n",ans%10007);
}