题目
点这里看题目。
分析
对于任何一个合法的矩形 ((x_1,y_1,x_2,y_2))，([x_1,x_2]) 和 ([y_1,y_2]) 分别是行和列上的一个区间。由于合法的矩形还没啥比较好的性质，我们可以对于矩阵进行分治，每次对于行和列中较长者进行切分，并且计算某一维跨过了划分点的合法矩形的个数。
不妨假设我们对于列划分，由于我们计算的是跨过中心列 (mi) 的矩形，所以中心列左侧需要求的是“匚”型，右侧恰好对称。于是我们只考虑左侧的统计方法。先暴力一点，我们可以枚举“匚”的上边界、下边界分别为第 (u) 行和第 (v) 行。预处理 (mathrm{le/ri/up/dn}[i][j]) 分别表示 ((i,j)) 向左、右、上、下四个方向，最远同色块的列号/行号。因此对于第 (u) 行和第 (v) 行，我们需要的结果为：
[sum_{i=max{mathrm{le}[u][mi],mathrm{le}[v][mi]}}^{mi}[mathrm{dn}[u][i]ge v]
]
由于 (i) 的下界要么为 (mathrm{le}[u][mi])，要么是 (mathrm{le}[v][mi])，我们可以对这两种情况分别预处理出结果，实际询问的时候再套用 (mathrm{le}) 较大的一个的答案。考虑固定 (u)，我们假设 (mathrm{le}[u][mi]) 成为较大值，这样我们就可以枚举 (i)。此时 ((u,i)) 会对于 (i<vle mathrm{dn}[u][i]) 的 (v) 造成贡献，直接差分即可。相应地，我们也可以固定 (v)，枚举 (i)。此时则是由 ((v,i)) 对于 (mathrm{up}[v][i]le u<i) 的 (u) 造成贡献，同样差分。
最终计算答案的时候，我们枚举 (u,v)，将左侧上边界为第 (u) 行，下边界为第 (v) 行的“匚”的数量和右侧对称形的数量相乘即可，注意判断能否拼起来。
考虑这样做的复杂度。对于一个 (p imes q) 的矩形分治的时候，单层复杂度为 (O(min{p,q}(p+q))le O(pq))，因此可以保证分治过程中每一层的复杂度为 (O(nm))，有 (O(log n)) 层，复杂度即为 (O(nmlog n))。
小结：
- 此处由于行、列均可以被表示到区间上，我们可以分治；由于行、列对称，我们可以选择较长的一维划分，保证复杂度。注意一下利用 (min) 来优化复杂度的方式，通常这意味着对称性。
- 统计过程中优化复杂度的方法是对于每种可能的情况都算一遍，来规避枚举到了 (u,v) 才知道 (i) 的边界的情况。这适用于实际情况较少，可以暴力处理每种情况的时候，类似的有 「NOI2021」量子通信中规避“在线”的方法。
代码
#include <cstdio>
#include <iostream>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int MAXN = 2005;
template<typename _T>
void read( _T &x )/*{{{*/
{
x = 0; char s = getchar(); int f = 1;
while( ! ( '0' <= s && s <= '9' ) ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
x *= f;
}/*}}}*/
template<typename _T>
void write( _T x )/*{{{*/
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}/*}}}*/
int thkL[MAXN][MAXN], thkR[MAXN][MAXN];
int up[MAXN][MAXN], dn[MAXN][MAXN];
int lef[MAXN][MAXN], rig[MAXN][MAXN];
char grid[MAXN][MAXN];
LL ans = 0;
int N, M;
void Divide( const int xL, const int xR, const int yL, const int yR )/*{{{*/
{
if( xL == xR || yL == yR ) return ;
if( xR - xL + 1 <= yR - yL + 1 )
{/*{{{*/
int mid = ( yR + yL ) >> 1, L, R;
rep( i, xL, xR ) rep( j, xL, xR ) thkL[i][j] = thkR[i][j] = 0;
rep( i, xL, xR )/*{{{*/
{
for( int j = mid ; j >= yL && j >= lef[i][mid] ; j -- )
thkL[i][std :: min( dn[i][j], xR )] ++,
thkL[i][std :: max( up[i][j], xL )] ++;
per( j, xR - 1, i ) thkL[i][j] += thkL[i][j + 1];
rep( j, xL + 1, i ) thkL[i][j] += thkL[i][j - 1];
for( int j = mid + 1 ; j <= yR && j <= rig[i][mid + 1] ; j ++ )
thkR[i][std :: min( dn[i][j], xR )] ++,
thkR[i][std :: max( up[i][j], xL )] ++;
per( j, xR - 1, i ) thkR[i][j] += thkR[i][j + 1];
rep( j, xL + 1, i ) thkR[i][j] += thkR[i][j - 1];
}/*}}}*/
rep( i, xL, xR ) rep( j, i + 1, xR )/*{{{*/
{
if( grid[i][mid] ^ grid[j][mid] ) continue;
if( grid[i][mid] ^ grid[i][mid + 1] ) continue;
if( grid[i][mid] ^ grid[j][mid + 1] ) continue;
L = lef[i][mid] >= lef[j][mid] ? thkL[i][j] : thkL[j][i];
R = rig[i][mid + 1] <= rig[j][mid + 1] ? thkR[i][j] : thkR[j][i];
ans += 1ll * L * R;
}/*}}}*/
Divide( xL, xR, yL, mid );
Divide( xL, xR, mid + 1, yR );
}/*}}}*/
else
{/*{{{*/
int mid = ( xR + xL ) >> 1, L, R;
rep( i, yL, yR ) rep( j, yL, yR ) thkL[i][j] = thkR[i][j] = 0;
rep( i, yL, yR )/*{{{*/
{
for( int j = mid ; j >= xL && j >= up[mid][i] ; j -- )
thkL[i][std :: min( rig[j][i], yR )] ++,
thkL[i][std :: max( lef[j][i], yL )] ++;
per( j, yR - 1, i ) thkL[i][j] += thkL[i][j + 1];
rep( j, yL + 1, i ) thkL[i][j] += thkL[i][j - 1];
for( int j = mid + 1 ; j <= xR && j <= dn[mid + 1][i] ; j ++ )
thkR[i][std :: min( rig[j][i], yR )] ++,
thkR[i][std :: max( lef[j][i], yL )] ++;
per( j, yR - 1, i ) thkR[i][j] += thkR[i][j + 1];
rep( j, yL + 1, i ) thkR[i][j] += thkR[i][j - 1];
}/*}}}*/
rep( i, yL, yR ) rep( j, i + 1, yR )/*{{{*/
{
if( grid[mid][i] ^ grid[mid][j] ) continue;
if( grid[mid][i] ^ grid[mid + 1][i] ) continue;
if( grid[mid][i] ^ grid[mid + 1][j] ) continue;
L = up[mid][i] >= up[mid][j] ? thkL[i][j] : thkL[j][i];
R = dn[mid][i] <= dn[mid][j] ? thkR[i][j] : thkR[j][i];
ans += 1ll * L * R;
}/*}}}*/
Divide( xL, mid, yL, yR );
Divide( mid + 1, xR, yL, yR );
}/*}}}*/
}/*}}}*/
int main()
{
read( N ), read( M );
rep( i, 1, N ) scanf( "%s", grid[i] + 1 );
rep( i, 1, N ) rep( j, 1, M )
{
up[i][j] = i > 1 && grid[i][j] == grid[i - 1][j] ? up[i - 1][j] : i;
lef[i][j] = j > 1 && grid[i][j] == grid[i][j - 1] ? lef[i][j - 1] : j;
}
per( i, N, 1 ) per( j, M, 1 )
{
dn[i][j] = i < N && grid[i][j] == grid[i + 1][j] ? dn[i + 1][j] : i;
rig[i][j] = j < M && grid[i][j] == grid[i][j + 1] ? rig[i][j + 1] : j;
}
Divide( 1, N, 1, M );
write( ans ), putchar( '
' );
return 0;
}