\(\mathcal{Description}\)

给定一张 \(n\times m\) 的表格，每个格子上写有一个小写字母。求其中长宽至少为 \(2\)，且边界格子上字母相同的矩形个数。

\(n,m\le2\times10^3\)。

\(\mathcal{Solution}\)

可以感知到这是道分治题。

不妨设当前处理左上角 \((u,l)\)，右下角 \((d,r)\) 的矩形内的所有答案，且 \(d-u>r-l\)。那么取行的一半 \(p=\lfloor\frac{u+d}{2}\rfloor\)，尝试求出所有在矩形内且跨过 \(p\) 这条水平直线的矩形数量。对于 \(p\) 上的每个点 \((p,i)\)，预处理出其向上/向下走到的同种格子中，有多少个能向左/向右走 \(x\) 步，然后枚举矩形跨过 \(p\) 的两个位置 \(i,j\)，讨论 \(i,j\) 向上/向下能走步数的大小关系，利用预处理的信息计算答案。

这样每层做到 \(\mathcal O((d-u)(r-l))\)，所以总复杂度 \(\mathcal O(nm(\log n+\log m))\)。

\(\mathcal{Code}\)

/*~Rainybunny~*/

#include <bits/stdc++.h>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

typedef long long LL;

inline int imin( const int a, const int b ) { return a < b ? a : b; }

inline int imax( const int a, const int b ) { return a < b ? b : a; }

const int MAXN = 2e3;

int n, m;

int up[MAXN + 5][MAXN + 5], dn[MAXN + 5][MAXN + 5];

int le[MAXN + 5][MAXN + 5], ri[MAXN + 5][MAXN + 5];

int sum[MAXN + 5][MAXN + 5][4];

char grid[MAXN + 5][MAXN + 5];

LL ans;

inline void solve( const int u, const int d, const int l, const int r ) {

    if ( u + 1 > d || l + 1 > r ) return ;

    if ( d - u > r - l ) {

        int mr = u + d >> 1, lr = r - l + 1;

        solve( u, mr, l, r ), solve( mr + 1, d, l, r );

        rep ( i, l, r ) rep ( j, 0, lr ) {

            sum[i][j][0] = sum[i][j][1] = sum[i][j][2] = sum[i][j][3] = 0;

        }

        rep ( i, l, r ) {

            rep ( j, imax( u, mr - up[mr][i] + 1 ),

              imin( d, mr + dn[mr][i] - 1 ) ) {

                ++sum[i][imin( ri[j][i], lr )][( mr < j ) * 2];

                ++sum[i][imin( le[j][i], lr )][( mr < j ) * 2 + 1];

            }

            per ( j, lr - 1, 0 ) rep ( k, 0, 3 ) {

                sum[i][j][k] += sum[i][j + 1][k];

            }

        }

        rep ( i, l, r ) rep ( j, i + 1, r ) {

            if ( grid[mr][i] == grid[mr][j] ) {

                ans += 1ll *

                  ( up[mr][i] < up[mr][j] ?

                  sum[i][j - i + 1][0] : sum[j][j - i + 1][1] ) *

                  ( dn[mr][i] < dn[mr][j] ?

                  sum[i][j - i + 1][2] : sum[j][j - i + 1][3] );

            }

        }

    } else {

        int mc = l + r >> 1, ud = d - u + 1;

        solve( u, d, l, mc ), solve( u, d, mc + 1, r );

        rep ( i, u, d ) rep ( j, 0, ud ) {

            sum[i][j][0] = sum[i][j][1] = sum[i][j][2] = sum[i][j][3] = 0;

        }

        rep ( i, u, d ) {

            rep ( j, imax( l, mc - le[i][mc] + 1 ),

              imin( r, mc + ri[i][mc] - 1 ) ) {

                ++sum[i][imin( dn[i][j], ud )][( mc < j ) * 2];

                ++sum[i][imin( up[i][j], ud )][( mc < j ) * 2 + 1];

            }

            per ( j, ud - 1, 0 ) rep ( k, 0, 3 ) {

                sum[i][j][k] += sum[i][j + 1][k];

            }

        }

        rep ( i, u, d ) rep ( j, i + 1, d ) {

            if ( grid[i][mc] == grid[j][mc] ) {

                ans += 1ll *

                  ( le[i][mc] < le[j][mc] ?

                  sum[i][j - i + 1][0] : sum[j][j - i + 1][1] ) *

                  ( ri[i][mc] < ri[j][mc] ?

                  sum[i][j - i + 1][2] : sum[j][j - i + 1][3] );

            }

        }

    }

}

int main() {

    scanf( "%d %d", &n, &m );

    rep ( i, 1, n ) scanf( "%s", grid[i] + 1 );

    rep ( i, 1, n ) rep ( j, 1, m ) {

        le[i][j] = grid[i][j] == grid[i][j - 1] ? le[i][j - 1] + 1 : 1;

        up[i][j] = grid[i][j] == grid[i - 1][j] ? up[i - 1][j] + 1 : 1;

    }

    per ( i, n, 1 ) per ( j, m, 1 ) {

        ri[i][j] = grid[i][j] == grid[i][j + 1] ? ri[i][j + 1] + 1 : 1;

        dn[i][j] = grid[i][j] == grid[i + 1][j] ? dn[i + 1][j] + 1 : 1;

    }

    solve( 1, n, 1, m );

    printf( "%lld\n", ans );

    return 0;

}

巴特西

Solution -「Gym 102956F」Border Similarity Undertaking

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章