#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
class FenwickTree {
private:
int sz;
vector<int> tree;
public:
FenwickTree() {}
FenwickTree(int n) : sz(n) { tree.assign(sz, 0); }
void Update(int p, int x) {
for (int i = p + 1; i <= sz; i += (i & -i)) {
tree[i - 1] += x;
}
}
int Query(int p) {
int res = 0;
for (int i = p + 1; i > 0; i -= (i & -i)) {
res += tree[i - 1];
}
return res;
}
};
struct event_t {
int type;
int r2, c2;
event_t() {}
event_t(int t, int r, int c) : type(t), r2(r), c2(c) {}
bool operator < (const event_t &o) const {
return make_pair(r2, type) < make_pair(o.r2, o.type);
}
};
vector<pair<int, int>> get_pairs(vector<int> a) {
int n = a.size();
vector<int> L(n, -1), R(n, n);
{ // Find the nearest value greater than a[i] on its left and right
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) L[i] = s.top();
s.emplace(i);
}
while (!s.empty()) s.pop();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) R[i] = s.top();
s.emplace(i);
}
}
vector<pair<int, int>> pairs; // valid pairs
for (int i = 0; i < n; i++) {
if (L[i] == -1 || R[i] == n) continue;
pairs.emplace_back(L[i] + 1, R[i] - 1);
}
sort(begin(pairs), end(pairs));
pairs.resize(unique(begin(pairs), end(pairs)) - begin(pairs));
return pairs;
}
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
long long ans = 0;
// valid pairs where (i, j) is one of its cell in the pairs
vector<vector<vector<int>>> go_r(n, vector<vector<int>>(m));
vector<vector<vector<int>>> go_d(n, vector<vector<int>>(m));
{ // Find valid pairs for each row and column
// Find valid pairs in each row
for (int i = 1; i < n - 1; i++) {
vector<pair<int, int>> pairs = get_pairs(a[i]);
for (auto j : pairs) {
go_r[i][j.first].emplace_back(j.second);
}
}
// Find valid pairs in each column
for (int i = 1; i < m - 1; i++) {
vector<int> cur;
for (int j = 0; j < n; j++) {
cur.emplace_back(a[j][i]);
}
vector<pair<int, int>> pairs = get_pairs(cur);
for (auto j : pairs) {
go_d[j.first][i].emplace_back(j.second);
}
}
}
// how many valid pairs (c1, c2) in the bottomside of current row
vector<vector<pair<int, int>>> span_r(m, vector<pair<int, int>>(m, {-1, -1})); // (row start, row end)
// how many valid pairs (r1, r2) in the rightside of current column
vector<vector<pair<int, int>>> span_d(n, vector<pair<int, int>>(n, {-1, -1})); // (column start, column end)
FenwickTree BIT(m);
for (int r1 = n - 1; r1 >= 0; r1--) {
for (int c1 = m - 1; c1 >= 0; c1--) {
sort(begin(go_r[r1][c1]), end(go_r[r1][c1]));
sort(begin(go_d[r1][c1]), end(go_d[r1][c1]));
{ // Process valid pairs which originated from (r1, c1)
for (auto c2 : go_r[r1][c1]) {
if (span_r[c1][c2].first == r1 + 1) { // we can extend
span_r[c1][c2].first = r1;
} else { // we must start anew
span_r[c1][c2] = {r1, r1};
}
}
for (auto r2 : go_d[r1][c1]) {
if (span_d[r1][r2].first == c1 + 1) { // we can extend
span_d[r1][r2].first = c1;
} else { // we must start anew
span_d[r1][r2] = {c1, c1};
}
}
}
vector<event_t> events; // (type, (r2, c2)) type = 0 for insertion, type = 1 for query
{ // Process each valid pair sorted by r2
for (auto r2 : go_d[r1][c1]) {
events.emplace_back(0, r2, span_d[r1][r2].second);
}
for (auto c2 : go_r[r1][c1]) {
events.emplace_back(1, span_r[c1][c2].second, c2);
}
sort(begin(events), end(events));
}
for (auto event : events) {
if (event.type == 0) { // insert new column valid pair
BIT.Update(event.c2, +1);
} else { // query for number of rectangles current row valid pair can form with
ans += BIT.Query(m - 1) - BIT.Query(event.c2 - 1);
}
}
// Undo all updates
for (auto event : events) {
if (event.type == 0) {
BIT.Update(event.c2, -1);
}
}
}
}
return ans;
}
