#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int) 205;
bool hori[MAXN][MAXN][MAXN], verti[MAXN][MAXN][MAXN];
int ph[MAXN][MAXN][MAXN], pv[MAXN][MAXN][MAXN];
int nx[2505];
ll pre[2505][2505];
bool visited[2505][2505];
int mxx[4'250'050], mxy[4'250'050], mnx[4'250'050], mny[4'250'050];
int cc = 0;
void dfs(int i, int j, vector<vector<int>> &vc){
if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
return;
}
if(visited[i][j]) return;
visited[i][j] = 1;
mnx[cc] = min(mnx[cc], i);
mxx[cc] = max(mxx[cc], i);
mny[cc] = min(mny[cc], j);
mxy[cc] = max(mxy[cc], j);
dfs(i + 1, j, vc);
dfs(i - 1, j, vc);
dfs(i, j + 1, vc);
dfs(i, j - 1, vc);
}
int gtpre(int x1, int y1, int x2, int y2){
if(x1 == 0 && y1 == 0){
return pre[x2][y2];
}else if(x1 == 0){
return pre[x2][y2] - pre[x2][y1 - 1];
}else if(y1 == 0){
return pre[x2][y2] - pre[x1 - 1][y2];
}else{
return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}
}
long long count_rectangles(vector<vector<int>> a) {
ll ans = 0;
int n = a.size();
int m = a[0].size();
if(n <= 200 && m <= 200){
for(int i = 0; i < n; i++){
for(int j = 0; j + 1 < m; j++){
int mx = a[i][j + 1];
for(int l = j + 2; l < m; l++){
hori[i][j][l] = (min(a[i][l], a[i][j]) > mx);
mx = max(mx, a[i][l]);
if(mx > a[i][j]) break;
}
}
}
for(int j = 0; j < m; j++){
for(int i = 0; i + 1 < n; i++){
int mx = a[i + 1][j];
for(int k = i + 2; k < n; k++){
verti[i][j][k] = (min(a[k][j] , a[i][j]) > mx);
mx = max(mx, a[k][j]);
if(mx > a[i][j]) break;
}
}
}
for(int l = 3; l <= m; l++){
for(int j = 0; j <= m - l; j++){
for(int i = 0; i < n; i++){
int pre = (i == 0 ? 0 : ph[i - 1][j][l]);
ph[i][j][l] = pre + hori[i][j][j + l - 1];
}
}
}
for(int l = 3; l <= n; l++){
for(int i = 0; i <= n - l; i++){
for(int j = 0; j < m; j++){
int pre = (j == 0 ? 0 : pv[i][j - 1][l]);
pv[i][j][l] = pre + verti[i][j][i + l - 1];
}
}
}
for(int i = 0; i < n - 2; i++){
for(int j = 0; j < m - 2; j++){
for(int k = i + 2; k < n; k++){
for(int l = j + 2; l < m; l++){
int d1 = -ph[i][j][l - j + 1] + ph[k - 1][j][l - j + 1];
int d2 = -pv[i][j][k - i + 1] + pv[i][l - 1][k - i + 1];
if(d1 == k - i - 1 && d2 == l - j - 1)
ans++;
}
}
}
}
return ans;
}else if(n <= 3){
if(n <= 2) return 0;
ll ans = 0;
vector<pair<int, int>> ara;
int lastl = 0;
for(int i = 1; i < m - 1; i++){
if(min(a[0][i], a[2][i]) <= a[1][i]){
if(lastl != i - 1);
ara.push_back({lastl, i});
lastl = i;
}
}
if(lastl != m - 2) ara.push_back({lastl, m - 1});
for(auto u: ara){
int l = u.first, r = u.second;
stack<int> st;
for(int j = r; j >= l; j--){
while(!st.empty() && a[1][st.top()] <= a[1][j])
st.pop();
if(st.empty()){
nx[j] = r + 1;
}else{
nx[j] = st.top();
}
st.push(j);
}
for(int j = l; j < r - 1; j++){
int mx = a[1][j + 1];
int rr = nx[j + 1];
//cerr<<j<<" "<<r<<"\n";
//cerr<<a[1][j + 1]<<" "<<a[1][j]<<" "<<a[1][rr]<<endl;
while(rr <= r){
if(mx >= min(a[1][j], a[1][rr]))
break;
ans++;
mx = max(mx, a[1][rr]);
rr = nx[rr];
//cerr<<rr<<" ";
}
}
}
return ans;
}else{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0) pre[i][j] = a[i][j];
else if(i == 0) pre[i][j] = pre[i][j - 1] + a[i][j];
else if(j == 0) pre[i][j] = pre[i - 1][j] + a[i][j];
else pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(visited[i][j] || a[i][j] == 1){
continue;
}
dfs(i, j, a);
mnx[cc] = mxx[cc] = i;
mny[cc] = mxy[cc] = j;
int say = gtpre(mnx[cc], mny[cc], mxx[cc], mxy[cc]);
if(say == 0)
ans++;
cc++;
}
}
return ans;
}
}
