P10127 解题报告

elbissoPtImaerD · 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}