经典问题,但是我为什么不会呢?????
题意
给定一张 \(n\times m\) 的 01 矩阵,求出有多少个子矩阵使得子矩阵内没有 1。
\(n,m\le 10^3\)
分析
考虑枚举每一行,计算以该行上每个点为右下角的合法子矩形个数 \(\sum sum_{i,j}\),也就是说,计算左上角的个数使得左上角和该右下角形成的子矩形不包含 1。
其实到这里已经可以思考单调栈了,但是为了捋顺思路,我们还是考虑对于每一行,只有该列上方的第一个 1 会对子矩形大小产生限制,而在某一个 1 往左的比该 1 所在行数要靠前的那些 1 也不会产生限制。据此我们考虑单调栈,预处理 \(up_{i,j}\) 表示 \((i,j)\) 往上第一个 1 和它本身的距离,单调栈里维护一个递增的 \(up_{i,j}\) 和 \(\sum sum_{i,j}\),将比 \(up_{i,j}\) 大的点弹完后,令栈顶的列为 \(c\),由于单调栈 \(up\) 递增,\(sum_{i,c}\) 的答案可以直接继承到 \(sum_{i,j}\) 中,额外的贡献还有 \(x\in(up_{i,c},up_{i,j}],y\in (c,j]\) 这部分子矩形的点,把它们加进 \(sum_{i,j}\) 中。
时间复杂度 \(O(nm)\)。
rep(j,1,m){
rep(i,1,n){
if(s[i][j]=='1')up[i][j]=0;
else up[i][j]=up[i-1][j]+1;
}
}
int ans=0;
rep(i,1,n){
tp=0;
sum[0]=0;
rep(j,1,m){
while(tp&&up[i][j]<=up[i][sta[tp]])--tp;
sum[j]=(sum[sta[tp]]+1ll*(j-sta[tp])*up[i][j]%mod)%mod;
ans=(ans+sum[j])%mod;
sta[++tp]=j;
}
}
标签:sum,矩阵,up,零子,计数问题,矩形,rep,单调
From: https://www.cnblogs.com/dcytrl/p/18538111