#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
struct rect {
int x1, x2, y1, y2;
bool ok;
rect() {};
rect(int x1, int x2, int y1, int y2) {
this->x1 = x1;
this->x2 = x2;
this->y1 = y1;
this->y2 = y2;
this->ok = true;
}
};
bool operator<(const rect &a, const rect &b) {
return make_tuple(a.x1, a.x2, a.y1, a.y2) < make_tuple(b.x1, b.x2, b.y1, b.y2);
}
bool operator==(const rect &a, const rect &b) {
return make_tuple(a.x1, a.x2, a.y1, a.y2) == make_tuple(b.x1, b.x2, b.y1, b.y2);
}
int n, m;
int A[2507][2507], newA[2507][2507];
int L[2507][2507], R[2507][2507], U[2507][2507], D[2507][2507];
int LM[20][2507][2507];
int cnt[2507];
int ok_pow[2507];
vector<rect> candidates;
bool less_op(int a, int b) {
return a < b;
}
bool less_equal_op(int a, int b) {
return a <= b;
}
inline bool okx(int x) {
return x >= 1 && x <= n;
}
inline bool oky(int y) {
return y >= 1 && y <= m;
}
void calc_firsts(bool (*op)(int, int) ) {
for(int x = 1 ; x <= n ; x++) {
stack<int> S;
for(int y = 1 ; y <= m ; y++) {
while(!S.empty() && op(A[x][S.top()], A[x][y]))
S.pop();
if(S.empty())
L[x][y] = 0;
else
L[x][y] = S.top();
S.push(y);
}
}
for(int x = 1 ; x <= n ; x++) {
stack<int> S;
for(int y = m ; y >= 1 ; y--) {
while(!S.empty() && op(A[x][S.top()], A[x][y]))
S.pop();
if(S.empty())
R[x][y] = m + 1;
else
R[x][y] = S.top();
S.push(y);
}
}
for(int y = 1 ; y <= m ; y++) {
stack<int> S;
for(int x = 1 ; x <= n ; x++) {
while(!S.empty() && op(A[S.top()][y], A[x][y]))
S.pop();
if(S.empty())
U[x][y] = 0;
else
U[x][y] = S.top();
S.push(x);
}
}
for(int y = 1 ; y <= m ; y++) {
stack<int> S;
for(int x = n ; x >= 1 ; x--) {
while(!S.empty() && op(A[S.top()][y], A[x][y]))
S.pop();
if(S.empty())
D[x][y] = n + 1;
else
D[x][y] = S.top();
S.push(x);
}
}
}
void find_candidates() {
for(int x = 1 ; x <= n ; x++) {
for(int y = 1 ; y <= m ; y++) {
int x1 = U[x][y];
int x2 = D[x][y];
int y1 = L[x][y];
int y2 = R[x][y];
if(okx(x1) && okx(x2) && oky(y1) && oky(y2) && x1 + 1 < x2 && y1 + 1 < y2)
candidates.emplace_back(x1 + 1, x2 - 1, y1 + 1, y2 - 1);
}
}
}
int maxv(int x1, int x2, int y) {
int p = ok_pow[x2 - x1 + 1];
return max(LM[p][x1][y], LM[p][x2 - (1 << p) + 1][y]);
}
void calc_left() {
for(int x = 1 ; x <= n ; x++) {
stack<int> S;
for(int y = 1 ; y <= m ; y++) {
while(!S.empty() && A[x][S.top()] < A[x][y])
S.pop();
if(S.empty())
LM[0][x][y] = L[x][y] = 0;
else
LM[0][x][y] = L[x][y] = S.top();
S.push(y);
}
}
for(int k = 1 ; k < 20 ; k++)
for(int x = 1 ; x <= n ; x++)
for(int y = 1 ; y <= m ; y++)
LM[k][x][y] = max(LM[k - 1][x][y], okx(x + (1 << (k - 1))) ? LM[k - 1][x + (1 << (k - 1))][y] : 0);
}
void one_check() {
calc_left();
for(rect &r : candidates) {
if(maxv(r.x1, r.x2, r.y2 + 1) >= r.y1)
r.ok = false;
}
}
void mirror_swap() {
for(int x = 1 ; x <= n ; x++)
reverse(A[x] + 1, A[x] + m + 1);
for(rect &r : candidates) {
swap(r.y1, r.y2);
r.y1 = m - r.y1 + 1;
r.y2 = m - r.y2 + 1;
}
}
void swap_dim() {
for(int x = 1 ; x <= n ; x++)
for(int y = 1 ; y <= m ; y++)
newA[y][x] = A[x][y];
for(int x = 1 ; x <= n ; x++)
for(int y = 1 ; y <= m ; y++)
A[y][x] = newA[y][x];
for(rect &r : candidates) {
swap(r.x1, r.y1);
swap(r.x2, r.y2);
}
swap(n, m);
}
int count() {
int res = 0;
for(rect r : candidates)
if(r.ok)
res++;
return res;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
int pot = 0;
for(int i = 1 ; i <= max(n, m) ; i++) {
if((1 << (pot+1)) <= i)
pot++;
ok_pow[i] = pot;
}
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
A[i + 1][j + 1] = a[i][j];
calc_firsts(less_equal_op);
find_candidates();
//sort(candidates.begin(), candidates.end());
vector<rect> ncand;
int smaller;
memset(cnt, 0, sizeof cnt);
for(rect r : candidates)
cnt[r.x1]++;
smaller = 0;
for(int i = 0 ; i < 2507 ; i++) {
int d = cnt[i];
cnt[i] = smaller;
smaller += d;
}
ncand.resize(candidates.size());
for(rect r : candidates)
ncand[cnt[r.x1]++] = r;
swap(ncand, candidates);
memset(cnt, 0, sizeof cnt);
for(rect r : candidates)
cnt[r.x2]++;
smaller = 0;
for(int i = 0 ; i < 2507 ; i++) {
int d = cnt[i];
cnt[i] = smaller;
smaller += d;
}
ncand.resize(candidates.size());
for(rect r : candidates)
ncand[cnt[r.x2]++] = r;
swap(ncand, candidates);
memset(cnt, 0, sizeof cnt);
for(rect r : candidates)
cnt[r.y1]++;
smaller = 0;
for(int i = 0 ; i < 2507 ; i++) {
int d = cnt[i];
cnt[i] = smaller;
smaller += d;
}
ncand.resize(candidates.size());
for(rect r : candidates)
ncand[cnt[r.y1]++] = r;
swap(ncand, candidates);
memset(cnt, 0, sizeof cnt);
for(rect r : candidates)
cnt[r.y2]++;
smaller = 0;
for(int i = 0 ; i < 2507 ; i++) {
int d = cnt[i];
cnt[i] = smaller;
smaller += d;
}
ncand.resize(candidates.size());
for(rect r : candidates)
ncand[cnt[r.y2]++] = r;
swap(ncand, candidates);
candidates.resize(distance(candidates.begin(), unique(candidates.begin(), candidates.end())));
one_check();
//cout << count() << endl;
mirror_swap();
one_check();
//cout << count() << endl;
swap_dim();
one_check();
//cout << count() << endl;
mirror_swap();
one_check();
return count();
}
