#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
// #ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
// #else
// #define dbg(...) 17;
// #endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
template<class T> struct BIT {
vector<T> bit;
int n;
void init(int n_) {
n = n_;
bit.resize(n);
}
T sum(int r) {
T ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
return ret;
}
T sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
}
};
struct seg {
int t;
int l, r;
int x, y;
seg(int t_, int l_, int r_, int x_, int y_) {
t = t_, l = l_, r = r_, x = x_, y = y_;
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = (int) a.size();
int m = (int) a[0].size();
vector<vector<pair<int, int>>> rows(n);
vector<vector<pair<int, int>>> cols(m);
for (int i = 0; i < n; i++) {
vector<int> stk;
for (int j = 0; j < m; j++) {
while (sz(stk) && a[i][stk.back()] <= a[i][j]) {
if (stk.back() + 2 <= j)
rows[i].emplace_back(stk.back(), j);
stk.pop_back();
}
if (sz(stk) && stk.back() + 2 <= j)
rows[i].emplace_back(stk.back(), j);
stk.push_back(j);
}
}
for (int j = 0; j < m; j++) {
vector<int> stk;
for (int i = 0; i < n; i++) {
while (sz(stk) && a[stk.back()][j] <= a[i][j]) {
if (stk.back() + 2 <= i)
cols[j].emplace_back(stk.back(), i);
stk.pop_back();
}
if (sz(stk) && stk.back() + 2 <= i)
cols[j].emplace_back(stk.back(), i);
stk.push_back(i);
}
}
vector<vector<vector<seg>>> vert_corner(n + 5, vector<vector<seg>>(m + 5));
vector<vector<pair<int, int>>> vert(m, vector<pair<int, int>>(m, {-1, -1}));
for (int i = 0; i < n; i++) {
for (auto bar : rows[i]) {
if (vert[bar.first][bar.second] == make_pair(-1, -1)) {
vert[bar.first][bar.second] = {i, i};
} else {
if (vert[bar.first][bar.second].second + 1 == i) {
vert[bar.first][bar.second].second++;
} else {
int lo = vert[bar.first][bar.second].first;
int hi = vert[bar.first][bar.second].second;
// cout << "SEGV: " << lo << " " << hi << " " << bar.first << " " << bar.second << '\n';
for (int z = lo - 1; z <= hi + 1; z++) {
vert_corner[z + 1][bar.first + 1].emplace_back(1, bar.first + 1, bar.second + 1, lo, hi + 2);
}
vert[bar.first][bar.second] = {i, i};
}
}
}
if (i == n - 1) {
for (int x = 0; x < m; x++) {
for (int y = 0; y < m; y++) {
if (vert[x][y] == make_pair(-1, -1)) continue;
int lo = vert[x][y].first;
int hi = vert[x][y].second;
for (int z = lo - 1; z <= hi + 1; z ++) {
vert_corner[z + 1][x + 1].emplace_back(1, x + 1, y + 1, lo, hi + 2);
}
// cout << "SEGV: " << lo << " " << hi << " " << x << " " << y << '\n';
}
}
}
}
vector<vector<vector<seg>>> hori_corner(n + 5, vector<vector<seg>>(m + 5));
vector<vector<pair<int, int>>> hori(n, vector<pair<int, int>>(n, {-1, -1}));
for (int j = 0; j < m; j++) {
for (auto bar : cols[j]) {
if (hori[bar.first][bar.second] == make_pair(-1, -1)) {
hori[bar.first][bar.second] = {j, j};
} else {
if (hori[bar.first][bar.second].second + 1 == j) {
hori[bar.first][bar.second].second++;
} else {
int lo = hori[bar.first][bar.second].first;
int hi = hori[bar.first][bar.second].second;
// cout << "SEGH: " << lo << " " << hi << " " << bar.first << " " << bar.second << '\n';
for (int z = lo - 1; z <= hi + 1; z++) {
hori_corner[bar.first + 1][z + 1].emplace_back(0, bar.first + 1, bar.second + 1, lo, hi + 2);
}
hori[bar.first][bar.second] = {j, j};
}
}
}
if (j == m - 1) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (hori[x][y] == make_pair(-1, -1)) continue;
int lo = hori[x][y].first;
int hi = hori[x][y].second;
for (int z = lo - 1; z <= hi + 1; z++) {
hori_corner[x + 1][z + 1].emplace_back(0, x + 1, y + 1, lo, hi + 2);
}
// cout << "SEGH: " << lo << " " << hi << " " << x << " " << y << '\n';
}
}
}
}
int ans = 0;
BIT<int> B;
B.init(m + 5);
vector<int> cnt(m + 5);
for (int i = 0; i < n + 5; i++) {
for (int j = 0; j < m + 5; j++) {
vector<seg> segs;
for (auto s : hori_corner[i][j]) {
segs.push_back(s);
cnt[s.y]++;
if (cnt[s.y] == 1) B.add(s.y, 1);
// cout << s.y << " ADD\n";
}
for (auto s : vert_corner[i][j]) segs.push_back(s);
sort(segs.begin(), segs.end(), [](seg& one, seg& two) {
if (one.t == 0 && two.t == 0) {
return one.y <= two.y;
} else if (one.t == 0 && two.t == 1) {
if (one.y == two.r) return false;
return one.y <= two.r;
} else if (one.t == 1 && two.t == 0) {
if (one.r == two.y) return true;
return one.r <= two.y;
} else {
return one.r <= two.r;
}
});
for (int i1 = 0; i1 < sz(segs); i1++) {
for (int i2 = i1 + 1; i2 < sz(segs); i2++) {
if (segs[i1].t == segs[i2].t) continue;
if (segs[i1].t == 0) {
if (segs[i1].y >= segs[i2].r && segs[i2].y >= segs[i1].r) ans++;
} else {
swap(i1, i2);
if (segs[i1].y >= segs[i2].r && segs[i2].y >= segs[i1].r) ans++;
swap(i1, i2);
}
}
}
// for (int k = 0; k < (int) segs.size(); k++) {
// auto& s = segs[k];
// // if (k < (int) segs.size() - 1 && segs[k].t == segs[k + 1].t && segs[k].t == 1 && segs[k].r == segs[k + 1].r) continue;
// if (s.t == 0) {
// cnt[s.y]--;
// if (cnt[s.y] == 0) B.add(s.y, -1);
// // cout << s.y << " DELETE\n";
// } else {
// ans += B.sum(0, s.r);
// if (B.sum(0, s.r)) {
// cout << i - 1 << " " << j - 1 << "WORKS\n";
// }
// // cout << s.r << " QUERY\n";
// }
// }
// cout << '\n';
}
}
return ans;
}
