/*
ID: varunra2
LANG: C++
TASK: rectangles
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n, m;
void res(VVI& a, int n, int m) {
a.resize(n);
trav(x, a) x.resize(m);
}
void deb(VVI& a) {
debug("debugging");
trav(x, a) debug(x);
}
struct BIT {
VI fen;
int n;
void init(int _n) {
n = _n;
fen.resize(n);
}
void upd(int ind, int val = 1) {
ind++;
while (ind <= n) {
fen[ind - 1] += val;
ind += (ind & -ind);
}
}
int qry(int ind) {
int ret = 0;
ind++;
while (ind >= 1) {
ret += fen[ind - 1];
ind -= (ind & -ind);
}
return ret;
}
int qry(int l, int r) {
r = min(r, n - 1);
l = max(l, 0);
if (r < l) return 0;
return qry(r) - qry(l - 1);
}
};
struct sptable {
const int bits = 13;
int n;
VI log2;
VVI spt;
int id;
void init(VI& vals, int ID) {
id = ID;
n = sz(vals);
log2.resize(n + 1);
res(spt, n, bits);
log2[1] = 0;
for (int i = 2; i <= n; i++) {
log2[i] = log2[i / 2] + 1;
}
for (int i = 0; i < n; i++) {
spt[i][0] = vals[i];
}
for (int i = 1; i < bits; i++) {
for (int j = 0; j + (1 << i) <= n; j++) {
int val1 = spt[j][i - 1];
int val2 = spt[j + (1 << (i - 1))][i - 1];
if (id)
spt[j][i] = max(val1, val2);
else
spt[j][i] = min(val1, val2);
}
}
}
int qry(int l, int r) {
int j = log2[r - l + 1];
int val1 = spt[l][j];
int val2 = spt[r - (1 << j) + 1][j];
if (id) return max(val1, val2);
return min(val1, val2);
}
void deb() {
trav(x, spt) debug(x);
}
};
VII gen(VI& vals) {
VII ret;
// generate the possible sides in this row
VI inds;
for (int i = 0; i < sz(vals); i++) {
for (int j = sz(inds) - 1; j >= 0; j--) {
int ind = inds[j];
if (vals[ind] >= vals[i]) {
ret.PB(MP(ind, i));
break;
} else {
ret.PB(MP(ind, i));
}
// if(j > 0 and vals[inds[j - 1]] == vals[ind]) break;
}
while (!inds.empty() and vals[inds.back()] <= vals[i]) inds.pop_back();
inds.PB(i);
}
return ret;
}
VVI grid;
VVI igrid;
VVI nxt;
VVI prv;
vector<sptable> spmx;
vector<sptable> spmn;
void init(VVI& a) {
res(grid, n, m);
res(igrid, m, n);
res(nxt, n, m);
res(prv, n, m);
spmx.resize(n);
spmn.resize(n);
rep(i, 0, n) rep(j, 0, m) {
grid[i][j] = a[i][j];
igrid[j][i] = a[i][j];
}
}
VI genprv(VI& vals) {
// get first element before you strictly greater than you
VI ret(sz(vals));
stack<int> st;
for (int i = 0; i < sz(vals); i++) {
while (!st.empty() and vals[st.top()] < vals[i]) st.pop();
if (st.empty())
ret[i] = -1;
else
ret[i] = st.top();
st.push(i);
}
return ret;
}
VI gennxt(VI& vals) {
VI ret(sz(vals));
stack<int> st;
for (int i = sz(vals) - 1; ~i; i--) {
while (!st.empty() and vals[st.top()] < vals[i]) st.pop();
if (st.empty())
ret[i] = n;
else
ret[i] = st.top();
st.push(i);
}
return ret;
}
ll solve(int l, int r, int s, int e) {
if (r - l < 2) return 0ll;
// left, right, start, end
// this describes a rectangle
// we must solve this rectangle
ll ret = 0;
// we will solve it using a sweepline approach
VVI sweep;
BIT fen;
fen.init(e - s + 1);
// we have a few types of events
for (int i = s; i <= e; i++) {
// we have to calculate this element at some point in time
sweep.PB({i, 0});
}
for (int i = s; i <= e; i++) {
sweep.PB({spmx[i + 1].qry(l + 1, r - 1), 1, i});
}
sort(all(sweep));
reverse(all(sweep));
for (int i = 0; i < e - s + 1; i++) {
fen.upd(i, 1);
}
for (auto& x : sweep) {
int val, type;
val = x[0];
type = x[1];
if (val < s) break;
if (type == 1) {
fen.upd(x[2] - s, -1);
} else {
int ind = spmn[val - 1].qry(l + 1, r - 1) - 1;
// debug(ind);
// debug(val - 1);
// ind = INF;
// for (int i = l + 1; i <= r - 1; i++) {
// ind = min(ind, nxt[val - 1][i]);
// }
// ind--;
ret += fen.qry(val - s, min(ind, e) - s);
}
}
// this is not possible :thonk:
// [sweep]: {{6, 1, 6}, {6, 0}, {5, 0}, {4, 1, 5}, {4, 1, 4}, {4, 0}, {3, 1,
// 3}, {3, 0}} [l, r, s, e]: 4 7 3 6 [ret]: -1
// debug(sweep);
// debug(l, r, s, e);
// debug(ret);
return ret;
}
ll count_rectangles(VVI a) {
n = sz(a);
m = sz(a[0]);
// assert(n >= m);
init(a);
vector<VII> pos(n);
for (int i = 0; i < n; i++) {
pos[i] = gen(grid[i]);
}
for (int i = 0; i < m; i++) {
auto pr = genprv(igrid[i]);
auto nx = gennxt(igrid[i]);
for (int j = 0; j < n; j++) {
prv[j][i] = pr[j];
nxt[j][i] = nx[j];
}
}
for (int i = 0; i < n; i++) {
spmn[i].init(nxt[i], 0);
spmx[i].init(prv[i], 1);
}
vector<map<PII, bool>> there(n);
for (int i = 1; i < n - 1; i++) {
trav(x, pos[i]) there[i][x] = true;
}
// deb(prv);
// deb(nxt);
ll ret = 0;
// const PII bad1 = MP(2, 4);
// const int bad2 = 3;
for (int i = 1; i < n - 1; i++) {
for (auto& x : pos[i]) {
// debug(i, x);
int e;
if (there[i][x] == false) continue;
for (int j = i; j < n - 1; j++) {
// if (x == bad1 and i == bad2) debug("here1", x, i, j);
if (there[j][x] == false) break;
// if (x == bad1 and i == bad2) debug("here", x, i, j);
there[j][x] = false;
e = j;
}
ll cur = solve(x.x, x.y, i, e);
ret += cur;
// if (cur > 0) debug(cur, x.x, x.y, i, e);
}
}
const int bad = 3;
// spmn[bad].deb();
// debug(spmn[bad].qry(2, 3));
return ret;
}
