#include "rect.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
int inf = 1e9 + 7;
struct sparce_tab {
vector<vector<int>> sp;
vector<int> logs;
void init(int n, vector<int>&a) {
logs.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
logs[i] = logs[i / 2] + 1;
}
sp.assign(logs[n] + 1, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int j = 1; j <= logs[n]; j++) {
for (int i = 0; i < n; i++) {
sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1<<(j-1))]);
}
}
}
int answer(int lq, int rq) {
int leng = rq - lq;
int j = logs[leng];
return max(sp[j][lq], sp[j][rq - (1 << j)]);
}
};
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
if (n < 3 || m < 3)
return 0;
vector<int> s(m);
vector<int> ok(m);
for (int i = 0; i < m; i++) {
s[i] = a[1][i];
ok[i] = (a[1][i] < min(a[0][i], a[2][i]));
}
vector<int> prok(m + 1);
for (int i = 0; i < m; i++) {
prok[i + 1] = prok[i] + ok[i];
}
sparce_tab sp;
sp.init(m, s);
ll res = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = i; j < m - 1; j++) {
int maxi = sp.answer(i, j + 1);
int sum = prok[j + 1] - prok[i];
if (sum == (j - i + 1) && maxi < min(s[i - 1], s[j + 1])) {
res++;
}
}
}
return res;
}
/*
signed main() {
int n, a, b, c;
cin >> n >> a >> b >> c;
int m;
cin >> m;
vector<int> p(m), q(m);
for (int i = 0; i < m; i++) {
cin >> p[i] >> q[i];
}
auto res = find_split(n,a,b,c,p,q);
for (auto el : res) {
cout << el << ' ';
}
cout << endl;
}
*/
