题解：AT_abc420_f [ABC420F] kirinuki

· · 题解

题意就是求面积小于等于 K 且全为 . 的矩形数量。

面积小于等于 K 这个限制正常很不好处理。考虑分治。

假设现在处理到的矩形为 (l_x,r_x,l_y,r_y)，在矩形较长的那边取中点划分成两个矩形 (l_x,r_x,l_y,mid),(l_x,r_x,mid+1,r_y)（这里假设 y 方向是长边），递归求解。

类似一维分治，考虑统计跨过 mid 这条线的答案。

先悬线法找出从这条线出发左右两边最远延伸距离 L_y,R_y，然后枚举两个端点 l_x\le i\le j\le r_x 来限制矩形的高，这样就化为一维问题：左边有 \min_{k=i}^j\{L_k\} 个格子，右边有 \min_{k=i}^j\{R_k\} 个格子，求长度不超过 \frac{K}{j-i+1} 的跨过线的区间个数。这个随便推推就可以 O(1) 求。

考虑分析时间复杂度：悬线的过程复杂度是矩形大小，枚举端点是在短边进行的，也不会超过矩形大小，两维坐标都会递归对数次。所以复杂度是 O(nm(\log n+\log m)) 的，随便过。

代码特好写，输入可以用 string 规避动态数组。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+7;
const int N=5e5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,k,l[maxn],r[maxn];
string s[maxn];
int calc(int L,int R,int K){ // O(1) 算贡献
    int lm=min(L,K-1),rm=max(0ll,min(lm,K-R)); 
    return R*rm+(lm-rm)*K-lm*(lm+1)/2+rm*(rm+1)/2;
}
int cdq(int xl,int xr,int yl,int yr){
    if(xl==xr&&yl==yr) return s[xl][yl]=='.';
    if(xr-xl>yr-yl){
        int mid=(xl+xr)>>1;
        for(int i=yl;i<=yr;i++){ l[i]=r[i]=0;
            for(int j=mid;j>=xl&&s[j][i]=='.';j--) l[i]++;
            for(int j=mid+1;j<=xr&&s[j][i]=='.';j++) r[i]++;
        }
        int res=0;
        for(int i=yl;i<=yr;i++){
            int lmx=inf,rmx=inf;
            for(int j=i;j<=yr;j++){
                lmx=min(lmx,l[j]); rmx=min(rmx,r[j]);
                res+=calc(lmx,rmx,k/(j-i+1));
            }
        }
        return res+cdq(xl,mid,yl,yr)+cdq(mid+1,xr,yl,yr);
    }else{
        int mid=(yl+yr)>>1;
        for(int i=xl;i<=xr;i++){ l[i]=r[i]=0;
            for(int j=mid;j>=yl&&s[i][j]=='.';j--) l[i]++;
            for(int j=mid+1;j<=yr&&s[i][j]=='.';j++) r[i]++;
        }
        int res=0;
        for(int i=xl;i<=xr;i++){
            int lmx=inf,rmx=inf;
            for(int j=i;j<=xr;j++){
                lmx=min(lmx,l[j]); rmx=min(rmx,r[j]);
                res+=calc(lmx,rmx,k/(j-i+1));
            }
        }
        return res+cdq(xl,xr,yl,mid)+cdq(xl,xr,mid+1,yr);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k; 
    for(int i=1;i<=n;i++) cin>>s[i];
    cout<<cdq(1,n,0,m-1);
    return 0;
}