分享一个 \(O(nm\log m)\) 的方法。
分析
考虑每次在 \(x\) 轴上固定左端点，然后移动 \(x\) 轴上的右端点，并统计答案。
考虑如何统计一个 \(1\times n\) 的区域的贡献。
显然长度为 \(i\) 的区间有 \(n-i+1\) 个，所以贡献即为：
\[\begin{aligned} f(n)=&\sum^n_{i=1} i\left(n-i+1\right) \\ =&\sum^n_{i=1} \left(n+1\right)i-i^2 \\ =&\left(\left(n+1\right)\sum^n_{i=1} i\right)-\left(\sum^n_{i=1} i^2\right) \\ =&\left(\left(n+1\right)\frac{n\left(n+1\right)}{2}\right)-\frac{n\left(n+1\right)\left(2n+1\right)}{6} \\ =&\frac{n\left(n+1\right)^2}{2}-\frac{n\left(n+1\right)\left(2n+1\right)}{6} \\ =&\frac{n\left(n+1\right)\left(n+2\right)}{6} \\ \end{aligned} \]所以 \(x\) 轴左端点为 \(l\)，右端点为 \(r\)，高度为 \(h\) 的矩形区域的贡献为 \((r-l+1)\cdot f(h)\)。
用 \(m\) 个 deque 来记录 \(y=m\) 的不适宜种植的格子的位置，再用一个 set 记录当前被占用的格子的位置。
每次移动 \(r\) 都先将 \(x=r\) 的不适宜种植的格子加入 set 中，然后统计答案。
时间复杂度 \(O(nm\log m)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 2003
deque<int> lx[maxn];
int64_t f(int64_t n) {return n*(n+1)*(n+2)/6;}
string str;
set<int> s;
vector<int> dts[maxn];
int main()
{
int n, m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>str;
for(int j=1;j<=m;j++)
if(str[j-1]=='#') lx[j].emplace_back(i);
}
int64_t ans=0;
for(int i=1;i<=m;i++) lx[i].emplace_back(n+1);
for(int l=1;l<=n;l++)
{
s.clear();
s.emplace(0);
s.emplace(m+1);
int64_t sum=f(m);
for(int i=l;i<=n;i++) dts[i].clear();
for(int i=1;i<=m;i++)
if(lx[i].front()==l-1) lx[i].pop_front();
for(int i=1;i<=m;i++)
dts[lx[i].front()].emplace_back(i);
for(int r=l;r<=n;r++)
{
for(auto p:dts[r])
{
auto nxt=s.lower_bound(p);
auto pre=prev(nxt);
sum-=f(*nxt-*pre-1);
sum+=f(*nxt-p-1);
sum+=f(p-*pre-1);
s.emplace(p);
}
ans+=sum*(r-l+1);
}
}
cout<<ans<<'\n';
}