#include "rect.h"
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<int> LOG2;
const int INF = 1E8;
struct ST {
int n;
vector<int> seg;
ST (int N) : n(N), seg(2*N, 0) {}
void push(int pos, int num) {
pos += n;
seg[pos] = num;
}
void init() {
for (int i = n-1; i > 0; i--) {
seg[i] = max(seg[2*i], seg[2*i+1]);
}
}
int query(int l, int r) {
l += n; r += n + 1;
int ret = 0;
while (l < r) {
if(l&1) ret = max(ret, seg[l++]);
if(r&1) ret = max(ret, seg[--r]);
r >>= 1;
l >>= 1;
}
return ret;
}
void print() {
for (int i = 1; i <= LOG2[seg.size()]+1; i++) {
for (int j = (1<<(i-1)); j < (1<<i); j++) {
cout << seg[j] << " ";
}
cout << endl;
}
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
long long ans = 0;
LOG2.push_back(0);
LOG2.push_back(0);
for(int i = 2; i <= 5*max(n,m); i++) LOG2.push_back(LOG2[i/2]+1);
vector<ST> rowTrees(n, ST(m));
vector<ST> columnTrees(m, ST(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
rowTrees[i].push(j, a[i][j]);
columnTrees[j].push(i,a[i][j]);
}
}
for(int i = 0; i < n; i++) {
rowTrees[i].init();
}
for(int i = 0; i < m; i++) {
columnTrees[i].init();
}
for(int r_1 = 1; r_1 < n-1; r_1++) {
for (int c_1 = 1; c_1 < m-1; c_1++) {
for (int r_2 = r_1; r_2 < n-1; r_2++) {
for (int c_2 = c_1; c_2 < m-1; c_2++) {
bool valid = true;
// cout << "--------------------------\n";
for (int column = c_1; column <= c_2; column++) {
int num = columnTrees[column].query(r_1,r_2);
if (num >= a[r_1-1][column] || num >= a[r_2+1][column]) valid = false;
}
for (int row = r_1; row <= r_2; row++) {
int num = rowTrees[row].query(c_1,c_2);
// printf("row: %d, c_1: %d, c_2: %d, max: %d\n",row,c_1,c_2,num);
// rowTrees[row].print();
if (num >= a[row][c_1-1] || num >= a[row][c_2+1]) valid = false;
}
ans += valid;
// if(valid) printf("(%d, %d) && (%d, %d)\n", r_1, c_1, r_2, c_2);
}
}
}
}
return ans;
}
