## Editorial for Đếm các hình chữ nhật

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của ladpro98

#include <cstdio>
#include <iostream>
#include <cstring>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define long long long

const int N = 404;

using namespace std;
int a[N][N];
char s[N];
int n, m;
int h[N], L[N], R[N];
long memo[5][5][5];

long cal(int c1, int c2, int c3) {
long &ret = memo[c1][c2][c3];
if (ret >= 0) return ret;
ret = 0;
REP(j, 1, n) h[j] = 0;
REP(i, 1, m) {
REP(j, 1, n)
if (a[i][j] == c1 || a[i][j] == c2 || a[i][j] == c3)
++h[j]; else h[j] = 0;
REP(j, 1, n)
for(L[j] = j - 1; L[j] > 0 && h[L[j]] >= h[j]; L[j] = L[L[j]]);
REPD(j, n, 1)
for(R[j] = j + 1; R[j] <= n && h[R[j]] > h[j]; R[j] = R[R[j]]);
REP(j, 1, n)
if (h[j])
ret += (long)(j - L[j]) * (R[j] - j) * h[j];
}
return ret;
}

int main() {
freopen("CRECT.inp", "r", stdin);
scanf("%d %d\n", &m, &n);
REP(i, 1, m) {
scanf("%s\n", s + 1);
REP(j, 1, n)
a[i][j] = s[j] - 'A';
}
RESET(memo, -1);
long ans = 0;
FOR(i, 0, 5) FOR(j, 0, i) FOR(k, 0, j) {
ans += cal(i, i, i) + cal(j, j, j) + cal(k, k, k)
- cal(i, j, j) - cal(i, k, k) - cal(j, k, k)
+ cal(i, j, k);
}
cout << ans << endl;
return 0;
}


#### Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{\$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=411;
var
f1,f2:text;
a:array[0..MAXN,1..MAXN] of char;
h,stack,l,r:array[0..MAXN] of longint;
count:array['A'..'E','A'..'E','A'..'E'] of int64;
ok:array[0..MAXN] of boolean;
d:array['A'..'E'] of longint;
m,n,kq:longint;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
var
i,j:longint;
begin
for i:=1 to m do
begin
for j:=1 to n do read(f1,a[i,j]);
end;
end;
procedure left; inline;
var
i,top:longint;
begin
top:=0; stack[0]:=0;
for i:=1 to n do
begin
while (top>0) and (h[i]<=h[stack[top]]) do dec(top);
l[i]:=stack[top]+1;
inc(top); stack[top]:=i;
end;
end;
procedure right; inline;
var
i,top:longint;
begin
top:=0; stack[0]:=n+1;
for i:=n downto 1 do
begin
while (top>0) and (h[i]<=h[stack[top]]) do dec(top);
r[i]:=stack[top]-1;
inc(top); stack[top]:=i;
end;
end;
procedure refine; inline;
var
i,top:longint;
begin
top:=0; stack[0]:=0;
for i:=1 to n do
begin
while (top>0) and (h[i]<h[stack[top]]) do dec(top);
if h[i]=h[stack[top]] then ok[i]:=false;
inc(top); stack[top]:=i;
end;
end;
procedure done(var kq:int64); inline;
var
i,j,k,u,v:longint;
begin
kq:=0;
fillchar(h,sizeof(h),0);
for i:=1 to m do
begin
for j:=1 to n do
if d[a[i,j]]=1 then inc(h[j]) else h[j]:=0;
fillchar(ok,sizeof(ok),true);
left;
right;
refine;
for j:=1 to n do
begin
if not ok[j] then continue;
u:=l[j]; v:=r[j];
k:=max(h[u-1],h[v+1]);
inc(kq,(v-u+1)*(v-u+2)*(h[j]-k) div 2);
end;
end;
end;
function cal(c1,c2,c3:char):int64; inline;
var
kq:int64;
begin
fillchar(d,sizeof(d),0);
d[c1]:=1; d[c2]:=1; d[c3]:=1;
done(kq);
cal:=kq;
end;
procedure solve;
var
kq:int64;
ch1,ch2,ch3:char;
begin
kq:=0;
for ch1:='A' to 'E' do
for ch2:='A' to 'E' do
if ch2>=ch1 then
for ch3:='A' to 'E' do
if ((ch1=ch2) and (ch3>=ch2)) or ((ch2>ch1) and (ch3>ch2)) then
count[ch1,ch2,ch3]:=cal(ch1,ch2,ch3);
for ch1:='A' to 'E' do
for ch2:='A' to 'E' do
if ch2>ch1 then
for ch3:='A' to 'E' do
if ch3>ch2 then
kq:=kq+count[ch1,ch2,ch3]
-count[ch1,ch1,ch2]-count[ch1,ch1,ch3]-count[ch2,ch2,ch3]
+count[ch1,ch1,ch1]+count[ch2,ch2,ch2]+count[ch3,ch3,ch3];
writeln(f2,kq);
end;
begin
openF;
inp;
solve;
closeF;
end.


#### Code mẫu của ll931110

program CRECT;
const
input  = '';
output = '';
maxn = 400;
k: array[1..5] of char = ('A','B','C','D','E');
var
a: array[1..maxn,1..maxn] of char;
stack,h: array[0..maxn] of integer;
dp: array[0..maxn] of int64;
s: array[0..3] of integer;
m,n: integer;
res: int64;

procedure init;
var
f: text;
i,j: integer;
begin
assign(f, input);
reset(f);

for i := 1 to m do
begin
for j := 1 to n do read(f, a[i,j]);
end;

close(f);
end;

procedure precalc;
begin
res := 0;
s[0] := 0;
stack[0] := 0;
dp[0] := 0;
end;

function calc(x,y,z: integer): int64;
var
i,j,top,tmp: integer;
t: int64;
begin
fillchar(h, sizeof(h), 0);
h[0] := -1;
t := 0;

for i := 1 to m do
begin
for j := 1 to n do
if ((a[i,j] = k[x]) or (a[i,j] = k[y]) or (a[i,j] = k[z])) then inc(h[j]) else h[j] := 0;

top := 0;
for j := 1 to n do
begin
while h[j] <= h[stack[top]] do dec(top);
tmp := stack[top];

dp[j] := (j - tmp) * h[j] + dp[tmp];
t := t + dp[j];

inc(top);
stack[top] := j;
end;
end;

calc := t;
end;

procedure update;
var
t: int64;
begin
t := calc(s[1],s[2],s[3]);
t := t - calc(s[1],s[1],s[2]) - calc(s[2],s[2],s[3]) - calc(s[3],s[3],s[1]);
t := t + calc(s[1],s[1],s[1]) + calc(s[2],s[2],s[2]) + calc(s[3],s[3],s[3]);
res := res + t;
end;

procedure attempt(i: integer);
var
j: integer;
begin
for j := s[i - 1] + 1 to 5 do
begin
s[i] := j;
if i < 3 then attempt(i + 1) else update;
end;
end;

procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, res);
close(f);
end;

begin
init;
precalc;
attempt(1);
printresult;
end.