自动搬运

查看原文

来自洛谷，原作者为

	elbissoPtImaerD Just keep it Quiet, it'll be all right. :-)

搬运于2025-08-24 22:54:57，当前版本为作者最后更新于2024-03-07 10:22:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

没看懂官方题解。

下文 $n,m$ 同阶。

第一问枚举 $(x,y)$ 二分 $E_{x,y}$ 然后前缀和优化 check 即可做到 $O(n^2\log n)$。

考虑暴力怎么做：枚举 $(i,j)$，再枚举 $(x,y)$，统计删 $(i,j)$ 对 $E_{x,y}$ 的影响。

这样暴力做好像不大能优化，把贡献拆掉：枚举 $(x,y)$，对于每个 $(i,j)$ 统计删去 $(i,j)$ 对 $E_{x,y}$ 的影响，将影响挂在 $(i,j)$ 上。

这个好做。考虑对 $E_{x,y}$ 有贡献的最大全 $1$ 方形，将其中元素按和 $(x,y)$ 的曼哈顿距离分组，每组贡献相同。

每组可以拆成 $O(1)$ 个矩形，用二维差分维护矩形加，单点求值，即可做到 $O(n^3)$。

il void Solve()
{
  int n,m;rd(n),rd(m);
  ve<ve<int>>mp(n,ve<int>(m)),a=mp,E=a;
  for(int i=0;i<n;++i) {
    string s;rd(s);
    for(int j=0;j<m;++j) {
      mp[i][j]=a[i][j]=s[j]=='.';
      if(i) a[i][j]+=a[i-1][j];
      if(j) a[i][j]+=a[i][j-1];
      if(i&&j) a[i][j]-=a[i-1][j-1];
    }
  }
  auto F=[&](int x){return x*x;};
  LL s=0;
  ve<ve<LL>>b(n,ve<LL>(m));
  auto _M=[&](int x,int y,int xx,int yy,int w)
  {
    b[x][y]+=w;
    if(xx+1<n) b[xx+1][y]-=w;
    if(yy+1<m) b[x][yy+1]-=w;
    if(xx+1<n&&yy+1<m) b[xx+1][yy+1]+=w;
  };
  for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(mp[i][j]) {
    int e=[&]
    {
      int l=0,r=min(n,m);
      auto S=[&](int x,int y,int xx,int yy)
      {
        int s=a[xx][yy];
        if(x) s-=a[x-1][yy];
        if(y) s-=a[xx][y-1];
        if(x&&y) s+=a[x-1][y-1];
        return s;
      };
      auto chk=[&](int k)
      {
        if(i-k<0||i+k>=n||j-k<0||j+k>=m) return false;
        return S(i-k,j-k,i+k,j+k)==F(k*2+1);
      };
      for(int mid;l<r;) chk(mid=l+r+1>>1)?l=mid:r=mid-1;
      return l;
    }()+1;
    s+=E[i][j]=F(e);
    for(;--e;) {
      int w=-E[i][j]+F(e);
      _M(i-e,j-e,i-e,j+e-1,w);
      _M(i-e,j+e,i+e-1,j+e,w);
      _M(i+e,j-e+1,i+e,j+e,w);
      _M(i-e+1,j-e,i+e,j-e,w);
    }
  }
  for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
    if(i) b[i][j]+=b[i-1][j];
    if(j) b[i][j]+=b[i][j-1];
    if(i&&j) b[i][j]-=b[i-1][j-1];
  }
  wrt(s,'\n');
  for(int i=0;i<n;++i) for(int j=0;j<m;++j) wrt(mp[i][j]?s+b[i][j]-E[i][j]:-1," \n"[j==m-1]);
  return;
}

$\color{green}{\checkmark}$