#include "rect.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T>void maximize(T& a, T b){ if(a < b){ a = b; } } template<class T>void minimize(T& a, T b){ if(a > b){ a = b; } } vector<vector<int>>a; int n, m; namespace sub123{ bool check(int x, int y, int u, int v){ for(int i = x; i <= u; i++){ for(int j = y; j <= v; j++){ if(a[i][j] >= min(min(a[x - 1][j], a[u + 1][j]), min(a[i][y - 1], a[i][v + 1]))){ return false; } } } return true; } ll solve(){ int ans = 0; for(int x = 1; x < n; x++){ for(int y = 1; y < m; y++){ for(int u = x; u + 1 < n; u++){ for(int v = y; v + 1 < m; v++){ if(check(x, y, u, v)){ ans++; } } } } } return ans; } } namespace sub4{ const int lim = 702; int bit[lim], mxv[lim], bd[lim], bu[lim], rbd[lim], rbu[lim], up[lim][lim], down[lim][lim]; bitset<lim>can; vector<int>query[lim]; void update(int p){ for(p++; p < lim; p += p & -p){ bit[p]++; } } int get(int p){ int ans = 0; for(p++; p > 0; p -= p & -p){ ans += bit[p]; } return ans; } ll solve(){ for(int j = 0; j < m; j++){ vector<int>st; for(int i = 0; i < n; st.push_back(i++)){ while(!st.empty() && a[st.back()][j] < a[i][j]){ st.pop_back(); } up[i][j] = (st.empty() ? 0 : st.back()); } st.clear(); for(int i = n - 1; i > -1; st.push_back(i--)){ while(!st.empty() && a[st.back()][j] < a[i][j]){ st.pop_back(); } down[i][j] = (st.empty() ? n - 1 : st.back()); } } ll ans = 0; for(int l = 1; l < m; l++){ for(int i = 0; i < n; i++){ mxv[i] = bu[i] = can[i] = 0; } fill(bd, bd + n, n - 1); for(int r = l; r + 1 < m; r++){ for(int i = 0; i < n; i++){ maximize(mxv[i], a[i][r]); minimize(bd[i], down[i][r]); maximize(bu[i], up[i][r]); can[i] = mxv[i] < min(a[i][l - 1], a[i][r + 1]); } rbd[n - 1] = bd[n - 1]; for(int i = n - 2; i > -1; i--){ rbd[i] = !can[i + 1] ? i + 1 : rbd[i + 1]; } for(int i = n - 2; i > -1; i--){ query[min(rbd[i], bd[i])].push_back(i); } rbu[0] = bu[0]; for(int i = 1; i < n; i++){ rbu[i] = !can[i - 1] ? i - 1 : rbu[i - 1]; } memset(bit, 0, sizeof(bit)); for(int i = 1; i < n; i++){ update(max(bu[i], rbu[i])); for(int& j : query[i]){ ans += get(j) - j - 1; } query[i].clear(); } } } return ans; } } namespace sub5{ ll solve(){ int ans = 0; for(int l = 1; l < m; l++){ for(int r = l, mv = 0; r + 1 < m; r++){ maximize(mv, a[1][r]); if(a[1][r] >= min(a[0][r], a[2][r]) || mv >= a[1][l - 1]){ break; } if(mv < a[1][r + 1]){ ans++; } } } return ans; } } const int INF = 1e9; namespace sub6{ bool check_subtask(){ for(int i = 0; i < n; i++){ if(*max_element(a[i].begin(), a[i].end()) > 1){ return false; } } return true; } int cnt, min_x, max_x, min_y, max_y; void dfs(int x, int y){ if(x < 0 || x >= n || y < 0 || y >= m || a[x][y] == 1){ return; } cnt++; a[x][y] = 1; minimize(min_x, x); maximize(max_x, x); minimize(min_y, y); maximize(max_y, y); dfs(x - 1, y); dfs(x + 1, y); dfs(x, y - 1); dfs(x, y + 1); } ll solve(){ int ans = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(a[i][j] == 0){ cnt = max_x = max_y = 0; min_x = min_y = INF; dfs(i, j); if(min_x > 0 && max_x + 1 < n && min_y > 0 && max_y + 1 < m && cnt == (max_x - min_x + 1) * (max_y - min_y + 1)){ ans++; } } } } return ans; } } namespace sub7{ const int lim = 2505; int bit[lim], beg[lim][lim], lst[lim][lim]; vector<pair<int, int>>row[lim][lim], col[lim][lim]; void update(int p, int x){ for(p++; p < lim; p += p & -p){ bit[p] += x; } } int get(int p){ int ans = 0; for(p++; p > 0; p -= p & -p){ ans += bit[p]; } return ans; } ll solve(){ memset(lst, 0x3f, sizeof(lst)); for(int i = 0; i < n; i++){ vector<int>st; for(int j = 0; j < m; st.push_back(j++)){ while(!st.empty() && a[i][st.back()] <= a[i][j]){ if(st.size() > 1 && a[i][st.back()] < a[i][j]){ int l = st[int(st.size()) - 2] + 1, r = j - 1; if(lst[l][r] + 1 != i){ beg[l][r] = i; } row[lst[l][r] = i][r].push_back(make_pair(beg[l][r], l)); } st.pop_back(); } } } memset(lst, 0x3f, sizeof(lst)); for(int j = 0; j < m; j++){ vector<int>st; for(int i = 0; i < n; st.push_back(i++)){ while(!st.empty() && a[st.back()][j] <= a[i][j]){ if(st.size() > 1 && a[st.back()][j] < a[i][j]){ int l = st[int(st.size()) - 2] + 1, r = i - 1; if(lst[l][r] + 1 != j){ beg[l][r] = j; } col[r][lst[l][r] = j].push_back(make_pair(l, beg[l][r])); } st.pop_back(); } } } ll ans = 0; memset(bit, 0, sizeof(bit)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ sort(row[i][j].begin(), row[i][j].end(), greater<pair<int, int>>()); sort(col[i][j].begin(), col[i][j].end(), greater<pair<int, int>>()); int p = 0; for(auto& [r1, c1] : row[i][j]){ while(p < col[i][j].size() && col[i][j][p].first >= r1){ update(col[i][j][p++].second, 1); } ans += get(c1); } while(p-- > 0){ update(col[i][j][p].second, -1); } } } return ans; } } ll count_rectangles(vector<vector<int>>_a){ swap(a, _a); if(min(n = a.size(), m = a[0].size()) < 3){ return 0; } if(max(n = a.size(), m = a[0].size()) <= 200){ return sub123::solve(); } if(n == 3){ return sub5::solve(); } if(max(n, m) <= 700){ return sub4::solve(); } if(sub6::check_subtask()){ return sub6::solve(); } return sub7::solve(); }