题意：
对于一个只包含 . 和 z
的矩阵，当以下条件满足时：
- 该矩阵的行数列数相等。
- 该矩阵的第一行与最后一行的字符全是
z。
- 该矩阵从右上角到左下角的对角线上的字符全是
z。
我们称其为 Z 矩阵。
现在给定一个 n×mn×m 的矩阵，请你计算它有多少个子矩阵是 Z
矩阵。
输入格式
第一行两个整数 nn , mm 分别表示矩阵的行数和列数
(1≤n,m≤3×103)(1≤n,m≤3×103)。
接下来 nn 行, 每行包含 mm 个字符, 表示该矩阵。
输出格式
输出一行一个整数表示 Z 矩阵的数量。
样例输入
样例输出
思路：
好题，但不会！看题解学的，具体过程参考这位大佬的知乎。
https://zhuanlan.zhihu.com/p/486600382
简单说一下就是遍历对角线，在对角线上建树状数组，将每个连续的“z”看作一段，离线维护线段上每点的左右“z”各能到达的最远位置。然后遍历这个线段，维护每个点能到达后续点的的贡献，凡是能到达的后续点都可以利用到此点的贡献。(看不懂就看原dalao的知乎就完了)
然后贴出我的代码，虽然和大佬的代码基本一样，但是因为原代码的树状数组部分没给，我的写法与dalao还有一丝丝不同。
代码：
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
| #include <bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int g[N][N],L[N][N],R[N][N],t[N];
pair<int,int>line[2*N];
vector<int>del[2*N];
int cnt=0;
long long ans=0;
int lowbit(int x){
return x&(-x);
}
int query(int L,int R){
int s1=0,s2=0;
while(L>0){
s1+=t[L];
L-=lowbit(L);
}
while(R>0){
s2+=t[R];
R-=lowbit(R);
}
return s2-s1;
}
void add(int x,int w){
while(x<=cnt){
t[x]+=w;
x+=lowbit(x);
}
}
void solve(){
for(int i=1;i<=cnt;i++){
int L=line[i].first,R=line[i].second;
ans+=query(max(1,i-R+1)-1,i);
if(L>1)add(i,1);
if(L>1)del[min(cnt,i+L-1)].push_back(i);
for(int x:del[i])add(x,-1);
}
memset(t,0,sizeof(t));
for(int i=1;i<=cnt;i++)del[i].clear();
cnt=0;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
g[i][j]=c=='z';
ans+=c=='z';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j])L[i][j]=L[i][j-1]+1;
}
for(int j=m;j>=1;j--){
if(g[i][j])R[i][j]=R[i][j+1]+1;
}
}
for(int d=2;d<=n+m;d++){
for(int i=max(1,d-m);i<=min(n,d-1);i++){
int j=d-i;
if(!g[i][j]){
if(cnt)solve();
}else{
line[++cnt]={L[i][j],R[i][j]};
}
}
if(cnt)solve();
}
cout<<ans;
return 0;
}
|