本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-27 11:09:49

好像就我用了这个奇怪的 $O(nm\lpha(n) + m \log m)$ 做法，场上把两处 $n,m$ 写反没调出来。

前置知识

并查集，树状数组，单调队列。

Solution

考虑枚举矩形的最左侧的那一列，统计对应的合法矩形个数，最后相加即可。

令 $l_{i,j}$ 表示从格子 $(i,j)$ 开始，向右延申最多多少格子，不会碰到障碍，格子 $(i,j)$ 也计入统计。

那么，假设枚举到的是 $(x,c),(x+1,c),\cdots,(y,c)$，那么，假如不考虑矩形面积小于等于 $k$ 的限制，那么对应的合法矩形个数将是 $\min\limits_{i=x}^y l_{i,c}$。

也就是说，在不考虑面积限制的情况下，一种枚举方案对应的矩形合法方案数仅取决于其 $l$ 值最小的格子。

那么，考虑枚举这个 $l$ 值最小的格子，计算出有多少种合法的枚举左侧第一列的方案，使得这个格子是 $l$ 值最小的，那么假设不考虑面积限制，就可以直接得出答案了。

此处实现有一些简单的技巧：若同一列多个格子的 $l$ 值一致，那么行数更小的格子视作 $l$ 值更小；可以使用单调队列均摊 $O(1)$ 求出每个格子的同一列最近的 $l$ 值更小的格子。

现在考虑面积小于等于 $k$ 的限制。

假设枚举了 $(x,y)$ 作为 $l$ 值最小的格子，令其 $l$ 值为 $p$，且 $(l-1,y),(r+1,y)$ 分别是 $y$ 列中，与 $(x,y)$ 最近的行数更小且 $l$ 值更小的格子，与 $(x,y)$ 最近的行数更大且 $l$ 值更小的格子。

那么，原本没有面积限制的情况下，任意选择 $l \le a \le b \le r$，选中 $y$ 列的 $a$ 到 $b$ 行的格子都是一种合理的枚举方案。

但是若 $\lfloor \frac{b-a+1}{k}\rfloor \lt p$，那么实际上枚举 $(a,y),(a+1,y),\cdots,(b,y)$ 对应的合法矩形方案数仅会受到 $b-a+1$ 的值的约束，而不是当前 $(x,y)$ 的 $l$ 值 $p$ 的约束。

考虑先只统计 $\lfloor \frac{b-a+1}{k}\rfloor \ge p$，也就是 $b-a+1 \le \lfloor\frac{p}{k}\rfloor$ 的情况。

::::info[现在需要求解一个这样的问题] 有 $a+b-1$ 个从左到右排列的格子，一个非负整数 $lim$。

称从左边开始第 $a$ 个格子为中心格子。

那么现在需要选择不超过 $lim$ 个连续格子使得包含中心格子，问有多少种方案。
::::
:::::info[解决方案] 令 $x$ 表示从中心格子开始向左边数，一共有多少个格子被选中了。。

现在，需要对于 $\forall x \in [1,a]$，计算出对应的合法的右端点的个数。

可能存在一部分 $x$，其右端点的可选集合必然是 $[a,a+b-1]$，要满足这个，则 $x+b-1 \le lim$，即 $x \le lim-b+1$。

那么这一部分 $x$ 的总贡献就是 $\max(0,lim-b+1)\cdot b$。

对于 $x \gt lim-b+1$，其贡献将会是 $\max(0,lim-x+1)$。

这一部分的最小 $x$ 将会是 $\max(0,lim-b+1)+1$，最大的 $x$ 将会是 $\min(lim,a)$，分别求出贡献值，然后这一部分 $x$ 的贡献的累加形式是一个等差数列，刚才求解了最大值最小值，并且公差为 $1$，直接算总和就行了。

时间复杂度 $O(1)$。
:::::

最后，需要统计有多少种选择方案 $(a,y),(a+1,y),\cdots,(b,y)$ 满足 $\lfloor\frac{k}{b-a+1}\rfloor \lt \min\limits_{i=a}^b l_{i,y}$，每种此类方案都会再贡献 $\lfloor\frac{k}{b-a+1}\rfloor$ 的答案。

考虑从小到大枚举 $b-a+1$ 的值，计算有多少选择同一列连续 $b-a+1$ 行的方案，使得不覆盖任意一个 $l$ 值小于等于 $b-a+1$ 的点。

随着 $b-a+1$ 的增大，原来能覆盖的点不会变得不能覆盖，所以可以每次暴力更新能覆盖的点。

然后，对于一列中长度为 $len$ 的极大的连续可覆盖格子，其贡献的选择方案数是 $len-\lfloor\frac{k}{b-a+1}\rfloor+1$。

那么，考虑定义两个数组 $sum,cnt$，每个 $len$ 都会导致 $sum_{len} \leftarrow sum_{len}+len,cnt_{len}\leftarrow cnt_{len}+1$。

那么，当前 $b-a+1$ 对应的选择方案数就是：
$\sum\limits_{i=b-a+1}^n (sum_{i}-cnt_{i}\cdot(b-a)) = \sum\limits_{i=b-a+1}^nsum_i - (\sum\limits_{i=b-a+1}^{n}cnt_i)(b-a)$。

这个选择方案数乘上 $\lfloor\frac{k}{b-a+1}\rfloor$ 就是这个 $b-a+1$ 对应的答案总贡献了。

$sum,cnt$ 都可以用树状数组维护，同一列的极大连续可覆盖格子则可以用并查集维护。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=5e6+5;
struct UNIONFIND{
    int fa[maxn],siz[maxn];
    void init(){
        FOR(i,1,maxn-1)fa[i]=i,siz[i]=0;
    }
    int get(int x){
        return x==fa[x]?x:fa[x]=get(fa[x]);
    }
    void ms(int a,int b){
        if(get(a)!=get(b)){
            siz[get(b)]+=siz[get(a)];
            fa[get(a)]=get(b);
        }
    }
}uf;
struct BIT{
    ll sum[500005];
    int cnt[500005];
    int lowbit(int x){
        return x&-x;
    }  
    void add(int pos,int _v){
        for(;pos<=500004;pos+=lowbit(pos)){
            sum[pos]+=_v;
            cnt[pos]++;
        }
    }
    void del(int pos,int _v){
        for(;pos<=500004;pos+=lowbit(pos)){
            sum[pos]-=_v;
            cnt[pos]--;
        }
    }
    ll _qsum(int pos){
        ll res=0;
        for(;pos;pos-=lowbit(pos)){
            res+=sum[pos];
        }
        return res;
    }
    ll qsum(int l,int r){
        return _qsum(r)-_qsum(l-1);
    }
    int _qcnt(int pos){
        int res=0;
        for(;pos;pos-=lowbit(pos)){
            res+=cnt[pos];
        }
        return res;
    }
    int qcnt(int l,int r){
        return _qcnt(r)-_qcnt(l-1);
    }
}tree;
ll gas(ll s,ll t){
    return (s+t)*(t-s+1)\/2;
}
ll calc(ll lflen,ll rglen,ll lim){
    \/\/ 包括中点的左半部分 =lflen，包括中点的右半部分=rglen
    \/\/ lim：长度上限，要求包括中点
    \/\/ rglen+lfuse-1 <= lim
    \/\/ lfuse <= lim-rglen+1
    ll lfuse=lim-rglen+1;\/\/ 左边使用了 lfuse 个或以下时，右边可以填满
    ckmn(lfuse,lflen);
    ll ans=0;
    if(lfuse>0){
        ans+=rglen*lfuse;
    }
    ckmx(lfuse,0ll);

    \/\/ 左边使用 lfuse 以上的时候，将会限制长度为 lim
    ll lfmx=min(lflen,lim);\/\/ 左边最多选择多长
    \/\/ 左边选择 lfuse+1 的话，有 lim-(lfuse+1)
    if(lim-lfmx+1<=lim-(lfuse+1)+1){
        ans+=gas(lim-lfmx+1,lim-(lfuse+1)+1);
    }
    return ans;
}
vector<pii> ids[500005];
void solve(int id_of_test){
    int n,m,k;
    read(n);
    read(m);
    read(k);
    auto id=[&](int i,int j)->int{
        return (i-1)*m+j;
    };
    char s[n+5][m+5];
    FOR(i,1,n){
        scanf("%s",s[i]+1);
    }
    int rg[n+5][m+5];
    FOR(i,1,n){
        rg[i][m+1]=0;
        REP(j,m,1){
            if(s[i][j]=='.'){
                rg[i][j]=rg[i][j+1]+1;
            }else{
                rg[i][j]=0;
            }
        }
    }
    ll ans=0;
    FOR(col,1,m){
        int lef[n+5],rig[n+5];
        stack<int> stk;
        FOR(row,1,n){
            while(!stk.empty()&&rg[row][col]<rg[stk.top()][col]){
                stk.pop();
            }
            if(stk.empty())lef[row]=1;
            else lef[row]=stk.top()+1;
            stk.push(row);
        }
        while(!stk.empty())stk.pop();
        REP(row,n,1){
            while(!stk.empty()&&rg[row][col]<=rg[stk.top()][col]){
                stk.pop();
            }
            if(stk.empty())rig[row]=n;
            else rig[row]=stk.top()-1;
            stk.push(row);
        }
        FOR(row,1,n){
            if(rg[row][col]==0)continue;
            
            int lenlim=k\/rg[row][col];\/\/ k\/lenlim = rg[row][col]，将会是最高限制
            ans+=calc(row-lef[row]+1,rig[row]-row+1,lenlim)*rg[row][col];
         \/\/   printf("(%d,%d): [%d,%d] lenlim %d calc %d\n",row,col,lef[row],rig[row],k\/rg[row][col],calc(row-lef[row]+1,rig[row]-row+1,lenlim));
        }
    }
    
    FOR(i,1,n){
        FOR(j,1,m){
            if(rg[i][j])ids[rg[i][j]].eb(mkpr(i,j));
        }
    }
  \/\/  printf("preans %lld\n",ans);
    FOR(len,1,n){
        {
            if(k\/len==0)break;
            int up,dw;
            if(len==1)up=m;
            else up=k\/(len-1);
            dw=k\/len+1;
            ckmn(up,m);
        \/\/    printf("len %d add [%d,%d]\n",len,dw,up);
            \/\/ 所有 rg 小于等于 k\/len 的格子都不能放，
            \/\/ 所有大于当前 m\/len 限制的，全部都可以放进去了
            REP(i,up,dw){
                for(auto [x,y]:ids[i]){
                    if(x>=2){
                        if(uf.siz[uf.get(id(x-1,y))]){
                            tree.del(uf.siz[uf.get(id(x-1,y))],uf.siz[uf.get(id(x-1,y))]);
                        }
                    }
                    if(x<n){
                        if(uf.siz[uf.get(id(x+1,y))]){
                            tree.del(uf.siz[uf.get(id(x+1,y))],uf.siz[uf.get(id(x+1,y))]);
                        }
                    }
                    if(x>=2&&uf.siz[uf.get(id(x-1,y))]){
                        if(uf.siz[uf.get(id(x-1,y))]){
                            uf.ms(uf.get(id(x,y)),uf.get(id(x-1,y)));
                        }
                    }
                    if(x<n&&uf.siz[uf.get(id(x+1,y))]){
                        if(uf.siz[uf.get(id(x+1,y))]){
                            uf.ms(uf.get(id(x,y)),uf.get(id(x+1,y)));
                        }
                    }
                    uf.siz[uf.get(id(x,y))]++;
                    tree.add(uf.siz[uf.get(id(x,y))],uf.siz[uf.get(id(x,y))]);
                }
            }
            ans+=(tree.qsum(len,n)-1ll*tree.qcnt(len,n)*(len-1))*(k\/len);
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    uf.init();
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
\/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*\/