题解：AT_abc420_f [ABC420F] kirinuki

· · 题解

先预处理出每个位置可以向上延长几个，记作 a_{i,j}。

注意到 \lfloor\dfrac{k}{i}\rfloor 一共只有 \sqrt k 种，于是考虑按照 a 从大往小加入，然后你就知道连着的横的最多有 \lfloor\dfrac{k}{a_{i,j}}\rfloor 个，然后每次这个值变化的时候重构每种长度连续段的贡献，每次加入的时候维护连续段的长度和每种长度的出现次数即可。

时间复杂度 O(nm+m\sqrt k)，你会发现其实就是 O(nm+\min\{n,m\}\sqrt{k})=O(nm)。

::::info[code]

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fLL
#define double long double 
#define eps 1e-8
#define endl '\n'
using namespace std;
const int N=5e5+5;
int n,m,k,ans,res,f[N],cnt[N];
vector<int> a[N],l[N],r[N];
vector<char> c[N];
vector<bool> b[N];
vector<pair<int,int> > v[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    if(n>m){
        for(int i=1;i<=n;++i) a[i].resize(m+1),b[i].resize(m+1),c[i].resize(m+1),l[i].resize(m+1),r[i].resize(m+1);
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>c[i][j];
    } else{
        for(int i=1;i<=m;++i) a[i].resize(n+1),b[i].resize(n+1),c[i].resize(n+1),l[i].resize(n+1),r[i].resize(n+1);
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>c[j][i];
        swap(n,m);
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        if(c[i][j]=='#') a[i][j]=0;
        else{
            a[i][j]=1;
            if(i>1) a[i][j]+=a[i-1][j];
        }
        v[a[i][j]].emplace_back(make_pair(i,j));
    }
    for(int i=n;i;--i){
        if(i==n||k/i!=k/(i+1)){
            for(int j=1;j<=m;++j)
                if(j<=k/i) f[j]=j*(j+1)/2;
                else f[j]=j*(k/i)-(k/i)*(k/i+1)/2+(k/i);
            res=0;
            for(int j=1;j<=m;++j) res+=cnt[j]*f[j];
        }
        for(auto p:v[i]){
            int x=p.first,y=p.second;
            if((y>1&&b[x][y-1])&&(y<m&&b[x][y+1])){
                res-=f[(y-1)-l[x][y-1]+1]+f[r[x][y+1]-(y+1)+1],--cnt[(y-1)-l[x][y-1]+1],--cnt[r[x][y+1]-(y+1)+1];
                r[x][l[x][y-1]]=r[x][y+1],l[x][r[x][y+1]]=l[x][y-1];
                res+=f[r[x][y+1]-l[x][y-1]+1],++cnt[r[x][y+1]-l[x][y-1]+1];
            } else if(y>1&&b[x][y-1]){
                res-=f[(y-1)-l[x][y-1]+1],--cnt[(y-1)-l[x][y-1]+1];
                r[x][l[x][y-1]]=y,l[x][y]=l[x][y-1];
                res+=f[y-l[x][y-1]+1],++cnt[y-l[x][y-1]+1];
            } else if(y<m&&b[x][y+1]){
                res-=f[r[x][y+1]-(y+1)+1],--cnt[r[x][y+1]-(y+1)+1];
                l[x][r[x][y+1]]=y,r[x][y]=r[x][y+1];
                res+=f[r[x][y+1]-y+1],++cnt[r[x][y+1]-y+1];
            } else{
                res+=f[1],++cnt[1];
                l[x][y]=r[x][y]=y;
            }
            b[x][y]=1;
        }
        ans+=res;
    }
    cout<<ans<<endl;
    return 0;
}

::::