#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}
template<bool enabled>
struct Debug{
template<typename S, typename T = void> struct Tag_Printable : false_type {};
template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
template<typename S, typename T = void> struct Tag_Iterable: false_type {};
template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};
template<typename T, size_t N> struct Tuple_Printer{
template<typename S>
static S& print(S& stream, T const&t){
return Tuple_Printer<T, N-1>::print(stream, t) << ", " << get<N>(t);
}
};
template<typename T> struct Tuple_Printer<T, 0>{
template<typename S>
static S& print(S& stream, T const&t){
return stream << get<0>(t);
}
};
template<typename T, typename... Args>
Debug& print(T const&x, true_type, Args...){
#ifdef LOCAL_RUN
if(enabled){
cerr << boolalpha << x;
}
#endif // LOCAL_RUN
return *this;
}
template<typename T>
Debug& print(T const&x, false_type, true_type){
*this << "[";
bool first = true;
for(auto &e:x){
if(!first) *this << ", ";
*this << e;
first = false;
}
return *this << "]";
}
template<typename S, typename T>
Debug& print(pair<S, T> const&x, false_type, false_type){
return *this << "(" << x.first << ", " << x.second << ")";
}
template<typename... Args>
Debug& print(tuple<Args...> const&t, false_type, false_type){
return Tuple_Printer<decltype(t), sizeof...(Args)-1>::print(*this, t);
}
template<typename T>
Debug& operator<<(T const&x){
return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
}
};
Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " << x
vector<vector<int> > transposed(vector<vector<int> > const&v){
const int n = v.size(), m = v.empty() ? 0 : v[0].size();
vector<vector<int> > ret(m, vector<int>(n));
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
ret[j][i] = v[i][j];
}
}
return ret;
}
struct Range_And{
Range_And(){}
Range_And(int Y_, vector<pair<int, int> > const&v) : Y(Y_), data(Y){
for(auto const&e:v){
data[e.second].emplace_back(e.first);
}
for(auto &e:data){
sort(e.begin(), e.end());
e.erase(unique(e.begin(), e.end()), e.end());
}
}
// all points present in {x} x [y1, y2)
bool all(int x, int y1, int y2) const {
const int dy = y2-y1;
auto it = lower_bound(data[x].begin(), data[x].end(), y1);
return data[x].end() - it >= dy && it[dy-1]<y2;
//auto it2 = lower_bound(data[x].begin(), data[x].end(), y2);
//return it2-it == y2-y1;
}
int Y;
vector<vector<int> > data;
};
vector<Range_And> build_ds(int X, vector<vector<pair<int, int> > > const&v){
vector<Range_And> ret;
for(auto const&e:v){
ret.emplace_back(X, e);
}
return ret;
}
// compute good ranges
vector<vector<pair<int, int> > > precalc(vector<vector<int> > const&v, vector<vector<int> > *L, vector<vector<int> > *R){
const int X = v.size(), Y = v[0].size();
vector<vector<pair<int, int> > > ret(Y);
for(int i=0;i<X;++i){
stack<pair<int, int> > s; // value, y
auto cand = [&](int y, int h, vector<vector<int> > *w){
while(!s.empty() && s.top().first <= h){
const int y2 = s.top().second;
ret[abs(y-y2)].emplace_back(i, min(y, y2));
if(w) (*w)[i][y2] = y;
s.pop();
}
s.emplace(h, y);
};
for(int j=0;j<Y;++j){
cand(j, v[i][j], R);
}
while(!s.empty()) s.pop();
for(int j=Y-1;j>=0;--j){
cand(j, v[i][j], L);
}
}
/*for(auto &e:ret){
sort(e.begin(), e.end());
e.erase(unique(e.begin(), e.end()), e.end());
}*/
return ret;
}
ll count_rectangles(std::vector<std::vector<int> > a) {
const int X = a.size(), Y = a[0].size();
vector<vector<int> > right_larger(X, vector<int>(Y, -1)), left_larger(X, vector<int>(Y, -1));
auto const row_ranges = precalc(a, &left_larger, &right_larger);
auto const row_ds = build_ds(Y, row_ranges);
auto const col_ranges = precalc(transposed(a), nullptr, nullptr);
auto const col_ds = build_ds(X, col_ranges);
//debug << named(row_ranges) << "\n";
//debug << named(col_ranges) << "\n";
vector<tuple<int, int, int, int> > ret;
auto add_rec = [&](int x1, int x2, int y1, int y2){
ret.emplace_back(x1, x2, y1, y2);
//debug << "Rec: " << ret.back() << "\n";
};
for(int dx=2;dx<X;++dx){
for(auto const&u:col_ranges[dx]){
const int y = u.first, x = u.second;
// top left corner
if(y!=0){
//auto const tmp = row_cart[x+1].right_larger<false, true>(y-1, a[x+1][y-1]);
auto const tmp = right_larger[x+1][y-1];
//if(dx == 2) debug << u << " " << named(tmp) << "\n";
if(tmp!=-1){
const int y2 = tmp;
const int dy = y2-y+1;
if(dy != 1){
if(col_ds[dx].all(x, y, y2) && row_ds[dy].all(y-1, x+1, x+dx)){
add_rec(x+1, x+dx-1, y, y2-1);
}
}
}
}
// top right corner
if(y+1 != Y){
auto const tmp = left_larger[x+1][y+1];
if(tmp!=-1){
const int y2 = tmp;
const int dy = y-y2+1;
if(dy != 1){
if(col_ds[dx].all(x, y2+1, y+1) && row_ds[dy].all(y2, x+1, x+dx)){
add_rec(x+1, x+dx-1, y2+1, y);
}
}
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret.size();
}
