#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2505;
const int inf = 1e9;
typedef pair<int, int> pii;
typedef pair<pii, pii> rect;
set<rect> cands;
int prv[2][MAXN][MAXN];
int nxt[2][MAXN][MAXN];
int n, m;
void make(int store[][MAXN], bool rc, bool dir, vector<vector<int>> &a, int v) {
vector<pii> stck;
stck.push_back(pii(inf, -1));
int sz = (rc ? n : m);
for (int i = (dir ? sz-1 : 0); (dir ? i >= 0 : i < sz); (dir ? i-- : i++)) {
int cur = (rc) ? a[i][v] : a[v][i];
while (cur >= stck.back().first) stck.pop_back();
if (rc) store[i][v] = stck.back().second;
else store[v][i] = stck.back().second;
stck.push_back(pii(cur, i));
}
}
map<pii, vector<int>> occ[2]; // row, then column
int cnt_leq(vector<int> &v, int i) {
int mn = -1;
int mx = v.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (v[cur] <= i) mn = cur;
else mx = cur;
}
return mx;
}
void print(rect &r) {
cout << r.first.first << ' ' << r.first.second << ' ' << r.second.first << ' ' << r.second.second << '\n';
}
long long count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
for (int i = 0; i < n; i++) {
make(prv[0], 0, 0, a, i);
make(nxt[0], 0, 1, a, i);
}
for (int i = 0; i < m; i++) {
make(prv[1], 1, 0, a, i);
make(nxt[1], 1, 1, a, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int suc = 0;
for (int t = 0; t < 2; t++) {
int rcpos = (t ? i : j);
if (nxt[t][i][j] != -1 && prv[t][i][j] != -1) {
suc++;
if (nxt[t][i][j]) {
occ[t][pii(prv[t][i][j]+1, nxt[t][i][j]-1)].push_back(i^j^rcpos);
}
}
}
if (suc == 2) {
// cerr << i << ' ' << j << '\n';
cands.insert(rect(pii(prv[1][i][j]+1, prv[0][i][j]+1), pii(nxt[1][i][j]-1, nxt[0][i][j]-1)));
}
}
}
for (auto &it: occ[0]) {
sort(it.second.begin(), it.second.end());
int p = 0;
int pv = -1;
for (int i = 0; i < it.second.size(); i++) {
if (it.second[i] == pv) continue;
pv = it.second[i];
swap(it.second[p++], it.second[i]);
}
it.second.resize(p);
}
for (auto &it: occ[1]) {
sort(it.second.begin(), it.second.end());
int p = 0;
int pv = -1;
for (int i = 0; i < it.second.size(); i++) {
if (it.second[i] == pv) continue;
pv = it.second[i];
swap(it.second[p++], it.second[i]);
}
it.second.resize(p);
}
int ans = 0;
// cerr << cands.size() << '\n';
for (rect r: cands) {
// print(r);
pii up = r.first;
pii down = r.second;
pii xrange = pii(up.first, down.first);
pii yrange = pii(up.second, down.second);
if ((cnt_leq(occ[0][yrange], xrange.second)-cnt_leq(occ[0][yrange], xrange.first-1) == xrange.second-xrange.first+1)
&& (cnt_leq(occ[1][xrange], yrange.second)-cnt_leq(occ[1][xrange], yrange.first-1) == yrange.second-yrange.first+1)) {
// cerr << xrange.second-xrange.first+1 << ' ' << cnt_leq(occ[0][yrange], xrange.second)
// << ' ' << cnt_leq(occ[0][yrange], xrange.first-1) << '\n';
// print(r);
ans++;
}
}
return ans;
}
