[sub matrix quantity statistics] cf1181c flag sub matrix quantity statistics

Better look and feel ：
http://wangyaqii.top/2022/06/29/cf1181c-flag-zi-ju-zhen-shu-liang-tong-ji/

CF1181C Flag Sub matrix quantity statistics

Topic introduction

Topic link ：

https://codeforces.com/problemset/problem/1181/C

Ideas

Maintenance variables

Statistical submatrix generally needs to maintain some arrays , Most of them are vertical maintenance or horizontal maintenance .

This topic maintains two arrays ：

$d[i][j]$ : $(i,j)$ The position extends down to the maximum number of blocks of the same color

$r[i][j]$：$(i,j)$ The position extends to the right up to the number of blocks of the same color

Let's first consider the width $1$ The situation of , When calculating the contribution of the column, the maximum contribution that the column can reach horizontally to the right .

At the same time, it is necessary to maintain two horizontally extended minimum value arrays ：

$r[i][j]$ ： Prefix （ Horizontal array ） minimum value ,$(x,j)$ To $(i,j),x<i$ The minimum value of the horizontal right extension length , Guarantee $(x,j)$ To $(i,j)$ It's the same color , The minimum value is updated only when the color is the same

$r[i][j]$ As stated , But this $r[i][j]$ Is updated by using the above array （ See code for details ）

$lmn[i][j]$ : suffix （ Horizontal array ） minimum value ,$(x,j)$ To $(i,j),x>i$ The minimum value of the horizontal right extension length , Guarantee $(x,j)$ To $(i,j)$ It's the same color , The minimum value is updated only when the color is the same

---

Realization

First consider the width of 1 when , Whether the flag can be formed in the longitudinal direction

The following conditions （ The flag of satisfaction consists of three lines , As required ）

• $i+3\ast d[i][j]-1<=n$ The flag on the third line does not cross the line

• $d[i][j]==d[i+d[i][j]][j]$ The second and first lines are the same length

• $d[i+2\ast d[i][j]][j]>=d[i][j]$ The length of the third line Greater than or equal to The length of the upper row （ Please think about why , As long as it is greater than or equal to, it can be statistically ）

Vertical can form a flag , Then consider the contribution of changing the vertical flag .

Ask for contribution ：

Because every vertical flag that meets the conditions will seek contribution , Therefore, for each vertical flag, only the right is required .

Here are some examples ：

AAA

BBB

CCC

The leftmost column , Can form 3 In this case

Middle column , Can form 2 In this case

The rightmost column , Can form 1 In this case

It's all about , The total contribution is 3 + 2 + 1

In fact, that is $n(n+1)/2$, Or recursion $f[i]=f[i-1]+i$, The idea is basically the same

Then you need to contribute

We definitely need to find Minimum The current overall contribution can only be calculated by the length of the right extension of , The minimum right extension length needs to be 3 Minimum value of three parts .

Therefore, the above minimum value is required （ Prefixes and suffixes ） Array .

Why use suffix array ?

Here are some examples ： The columns that meet the conditions are marked in bold

A ( It doesn't matter )

A

A

B

B

C

C

C（ It doesn't matter ）

But there is one more letter above and below , If the minimum value is counted , The above section uses the prefix minimum array , The length of the first row extending to the right will be counted , Cause statistical errors . The following sections are the same .

So the above part needs to use the suffix array , The following sections need to use prefix arrays , The middle part doesn't matter

Then the contribution that the front row can make is $min(lmn[i][j],r[i+2\ast d[i][j]-1][j],r[i+3\ast d[i][j]-1][j])$

See the code for the specific overall implementation .

Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1005, mod = 1e9 + 7;

int d[N][N], r[N][N], lmn[N][N];
char s[N][N];

void solve()
{
    
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> (s[i] + 1);

	for(int i = n; i; i--)
	{
    
		for(int j = m; j; j--)
		{
    
			d[i][j] = d[i + 1][j], r[i][j] = r[i][j + 1];

			if(s[i][j] == s[i + 1][j])
				d[i][j] ++;
			else d[i][j] = 1;
			
			if(s[i][j] == s[i][j + 1])
				r[i][j] ++;
			else r[i][j] = 1;
		}
	}

	for(int i = n; i; i--)
		for(int j = 1; j <= m; j++)
		{
    
			lmn[i][j] = r[i][j];
			if(i < n && s[i + 1][j] == s[i][j])
				lmn[i][j] = min(lmn[i][j], lmn[i + 1][j]);
		}

	for(int i = 2; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
    
			if(s[i][j] == s[i - 1][j])
				r[i][j] = min(r[i][j], r[i - 1][j]);
		}


	ll ans = 0;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
    
			if(i + 3 * d[i][j] - 1 <= n && d[i][j] == d[i + d[i][j]][j] && d[i + 2 * d[i][j]][j] >= d[i][j])
				ans += min({
    lmn[i][j], r[i + 2 * d[i][j] - 1][j], r[i + 3 * d[i][j] - 1][j]});
		}

	cout << ans << "\n";
}
int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	// cin >> t;
	t = 1;
	while(t--)
		solve();
	return 0;
}