#include "rect.h"
#include <cstdio>
#include <algorithm>
using namespace std;
bool goodRect(int i, int j, int exp) {
return j - i - 1 > 0 && exp >= j - i - 1;
}
struct Column {
int l1, l2, c;
};
const int MAX_N = 2500;
const int MAX_L = 12;
vector<Column> getColumns(const vector<vector<int> > matr) {
int N = matr.size(), M = matr[0].size();
vector<int> stiva(N, 0);
vector<Column> rez;
int top;
for(int c = 0; c < M; ++c) {
top = 0;
for(int l = 0; l < N; ++l) {
bool eq = false;
while(top > 0 && matr[l][c] >= matr[stiva[top - 1]][c]) {
if(l - stiva[top - 1] > 1)
rez.push_back({stiva[top - 1], l, c});
if(matr[l][c] == matr[stiva[top - 1]][c])
eq = true;
--top;
}
if(!eq && top > 0 && l - stiva[top - 1] > 1)
rez.push_back({stiva[top - 1], l, c});
stiva[top++] = l;
}
}
return rez;
}
bool cmp(Column a, Column b) {
return a.l1 < b.l1 || (a.l1 == b.l1 && a.l2 < b.l2) || (a.l1 == b.l1 && a.l2 == b.l2 && a.c < b.c);
}
int mylog[1+MAX_N];
int rmqleft[MAX_L][MAX_N][MAX_N];
int rmqright[MAX_L][MAX_N][MAX_N];
void initRmq(const vector<vector<int> > &a) {
int N = a.size(), M = a[0].size();
vector<int> stiva(M);
int top;
for(int l = 0; l < N; ++l)
for(int c = 0; c < M; ++c) {
rmqleft[0][l][c] = 0;
rmqright[0][l][c] = M - 1;
}
for(int l = 0; l < N; ++l) {
top = 0;
for(int c = 0; c < M; ++c) {
bool eq = false;
while(top > 0 && a[l][c] >= a[l][stiva[top - 1]]) {
rmqright[0][l][stiva[top - 1]] = c;
if(a[l][stiva[top - 1]] == a[l][c]) {
rmqleft[0][l][c] = stiva[top - 1];
eq = true;
}
--top;
}
if(!eq && top > 0)
rmqleft[0][l][c] = stiva[top - 1];
stiva[top++] = c;
}
}
for(int lg = 1; lg < MAX_L; ++lg)
for(int l = 0; l < N; ++l)
for(int c = 0; c < M; ++c) {
rmqleft[lg][l][c] = max(rmqleft[lg - 1][l][c], rmqleft[lg - 1][l + (1 << (lg - 1))][c]);
rmqright[lg][l][c] = min(rmqright[lg - 1][l][c], rmqright[lg - 1][l + (1 << (lg - 1))][c]);
}
for(int i = 2; i <= MAX_N; ++i)
mylog[i] = mylog[i / 2] + 1;
}
int queryRmq(int c, int l1, int l2, bool left) {
int lg = mylog[l2 - l1 + 1];
if(left)
return max(rmqleft[lg][l1][c], rmqleft[lg][l2 - (1 << lg) + 1][c]);
else
return min(rmqright[lg][l1][c], rmqright[lg][l2 - (1 << lg) + 1][c]);
}
int aib[1+MAX_N];
static inline int lsb(int x) {
return x & (-x);
}
int limInf, limSup;
void update(int poz, int val) {
poz++;
while(poz <= limSup) {
aib[poz] += val;
poz += lsb(poz);
}
}
int query(int poz) {
int rez = 0;
poz++;
while(poz > limInf) {
rez += aib[poz];
poz -= lsb(poz);
}
return rez;
}
enum TypeEvent {
INSERT,
ERASE
};
struct Event {
TypeEvent type;
int x, c;
};
bool cmpEvent(Event &a, Event &b) {
return a.x < b.x || (a.x == b.x && a.type < b.type);
}
long long processRectangle(int c1, int c2, int l1, int l2) {
vector<Event> evs;
++l1;
--l2;
limInf = c1;
limSup = c2 + 1;
for(int c = c1; c <= c2; ++c) {
int left, right;
right = queryRmq(c, l1, l2, false);
evs.push_back({INSERT, c, c});
evs.push_back({ERASE, right, c});
}
sort(evs.begin(), evs.end(), cmpEvent);
int lastup = 0;
long long rez = 0LL;
for(int c = c1; c <= c2; ++c) {
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == INSERT) {
update(evs[lastup].c, 1);
++lastup;
}
int left = queryRmq(c, l1, l2, true);
rez = rez + query(max(c - 2, -1)) - query(max(left - 1, -1));
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == ERASE) {
update(evs[lastup].c, -1);
++lastup;
}
}
while(lastup < evs.size()) {
if(evs[lastup].type == INSERT)
update(evs[lastup].c, 1);
else
update(evs[lastup].c, -1);
++lastup;
}
return rez;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int N, M;
long long sum = 0LL;
N = a.size();
M = a[0].size();
initRmq(a);
vector<Column> rez;
rez = getColumns(a);
sort(rez.begin(), rez.end(), cmp);
int i, j;
i = j = 0;
while(i < rez.size()) {
while(j < rez.size() && rez[i].l1 == rez[j].l1 && rez[i].l2 == rez[j].l2 && rez[i].c + (j - i) == rez[j].c)
++j;
sum = sum + processRectangle(max(0, rez[i].c - 1), min(M - 1, rez[j - 1].c + 1), rez[i].l1, rez[i].l2);
i = j;
}
return sum;
}
