自动搬运

查看原文

来自洛谷，原作者为

	铃宕 **

搬运于2025-08-24 21:32:13，当前版本为作者最后更新于2019-02-18 22:16:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

使用单调栈求解 O（nm）

update 于 2019-8-11 ~~ 写得很差，建议还没看过的就不要看了 ~~

我们要解决的第一个问题是如何求总方案数

1. 对每一行统计以其为底边构造的长方形的数量(怎么求后面讲)

2. 每行的方案数之和及为总方案数（因为一个长方形不可能有两个底边，所以此方法可以保证不重不漏）

那么怎么求对每一行统计以其为底边构造的长方形的方案数呢？

首先我们了解一下什么是单调栈（不过神犇们都应该会了）

1.定义

单调栈是一种可以以 $O(n)$ 的时间复杂度解决类似求对于每一个数 $i$ 左边（或右边）第一个（从 $i$ 开始）比它小（或大）的数的问题的算法 （语文不好）

下面以求对于每一个数 $i$ 左边第一个（从 $i$ 开始）不大于它的数为例

2. 怎么做？

首先定义一个栈（先进后出）栈中存的是目前还没有答案的数，易得栈中元素递减（不然与栈的定义不符），对于每一次要将元素压入栈，先将栈顶所有大于它的元素记录答案（就是要压入的元素）并弹出，因为我们要求左边第一个，所以以从右向左的顺序入栈（因为是先入栈再记录答案，所以要从元素从答案入栈）

//代码，单调栈
void ddzl(){
    top=0;//清空栈
    for(int i=m;i>=1;i--){
        while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;//记录答案
        top++;
        k[top]=i;//入栈
    }
    while(top) l[k[top]]=0,top--;//对没有答案做特殊处理
}

扯了一堆，是时候说如何统计以其为底边构造的长方形的方案数了

1. 定义 $h_i$ 为当前行第 $i$ 列可向上延伸多少（即有多少为图画的块，如果当前块被图画那么值为$0$）

2. 使用单调栈算出 $l_i$ 和 $r_i$ ，分别是 $h$ 中左边第一个（从 $h_i$ 开始）不大于 $h_i$ 的数和右边第一个（从 $h_i$ 开始）小于 $h_i$ 的数

3. 对每一列求出被这一列的高度限制的长方形数，即为($i$ $-$ $l_i$)$\times$($r_i$ $-$ $i$)$\times$ $h_i$ 将所有列的答案相加就是以当前行为底边构造的长方形的方案数了

为什么第3步不会重复： 有重复是只有一种情况，即当 $l_i$ 到 $r_i$ 之间有一个 $j$ 使 $h_j$ 小于 $h_i$ ，但是这是不可能的，因为$l_i$ 和 $r_i$ 分别是 $h$ 中左边第一个（从 $h_i$ 开始）不大于 $h_i$ 的数和右边第一个（从 $h_i$ 开始）小于 $h_i$ 的数，所以在 $l_i$ 到 $r_i$ 之间不存在 $j$ 使 $h_j$ 小于 $h_i$

举个例子：

对于某条情况如下图的底边
（0为没图画，1为有图画）
     0 1 0 1 0 0
     1 0 1 0 1 0
     1 0 0 1 0 0
     1 0 1 0 0 0
   h:0 3 0 1 2 4
   l:0 1 0 3 4 5
   r:7 3 7 7 7 7
方案：0 3 0 3 4 4
总方案数：14，验算后发现没错

update:

关于一些问题的解答：

Q1：为什么公式是这样的呢？

解答： 对于每次求方案数，我们要先选底边（叫底边好像不太合理，凑合着看吧），由于我们是要求被这一列的高度限制的长方形数，所以底边必须包含这一列，那么底边左端点的方案数即为 $i$ $-$ $l_i$，同理右端点的方案数为 $r_i$ $-$ $i$，底边的方案数即为($i$ $-$ $l_i$)$\times$($r_i$ $-$ $i$)，而高的方案数则为 $h_i$ (不要理会这个称呼)，所以公式就是 ($i$ $-$ $l_i$)$\times$($r_i$ $-$ $i$)$\times$ $h_i$

Q2: 为什么 $l_i$ , $r_i$ 是一个不大于，一个小于呢?

解答：一个不大于，一个小于是因为如果有相邻的且 $h_i$ 相等 的，两个都是不大于会有重复，而两个都是小于有会有一些长方形没数到，而,一个不大于，一个小于是相当于去了重复的

时间复杂度

$O(nm)$，单调栈复杂度 $O(m)$ ,因为有 $n$ 行，所以复杂度为 $O(nm)$

code

#include<bits/bycx++.h>
using namespace std;
char ch;
long long l[1020],r[1020],h[1020],k[1020],n,m,top;
int d[1020][1020];
long long ans;
void ddzl(){//单调栈，前面的代码有注释
    top=0;
    for(int i=m;i>=1;i--){
        while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) l[k[top]]=0,top--;
}
void ddzr(){//同上
    top=0;
    for(int i=1;i<=m;i++){
        while(top!=0&&h[i]<h[k[top]]) r[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) r[k[top]]=m+1,top--;
}
void work(){
    ddzl();
    ddzr();//两次单调栈预处理l，r
    for(int i=1;i<=m;i++){
        ans+=(i-l[i])*(r[i]-i)*h[i];//统计
    } 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){//输入
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch=='*') d[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){h[j]++;if(d[i][j]) h[j]=0;}//预处理h
        work();统计当前行
    }
    cout<<ans;//输出
//} 不要抄代码

头文件防抄袭

有问题请私信作者