#include "rect.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
struct DSU{
int n, t;
vector<int> p;
DSU(int n, int t) : n(n), t(t), p(n) {
for(int i = 0; i < n; i++) p[i] = i;
}
int find(int u){
if(p[u] == u) return u;
return p[u] = find(p[u]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if(u == v) return;
if(u > v) swap(u, v);
if(t) p[u] = v;
else p[v] = u;
}
};
struct fenwick{
int n;
vector<int> fen;
fenwick(int n) : n(n), fen(n){}
void upd(int pos, int val){
for(; pos < n; pos |= pos + 1)
fen[pos] += val;
}
int query(int pos){
int ret = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ret += fen[pos];
return ret;
}
int query(int ql, int qr){
return query(qr) - query(ql - 1);
}
};
ll count_rectangles(vector<vector<int>> a){
int n = a.size(), m = a[0].size();
ll ans = 0;
auto compute = [&](int N, int M, vector<vector<int>> &aa){
vector<vector<pair<int, int>>> arr(N);
for(int i = 0; i < N; i++){
vector<pair<int, int>> vals;
vector<int> act(M);
DSU left(M, 0), right(M, 1);
for(int j = 0; j < M; j++)
vals.pb({aa[i][j], j});
sort(all(vals));
vector<vector<int>> same_idx(M);
int c = -1;
for(int k = 0, lst = -1; k < M; k++){
c += (lst != vals[k].first);
same_idx[c].pb(vals[k].second);
lst = vals[k].first;
}
same_idx.resize(c);
for(int j = 0; j < c; j++){
for(int ind : same_idx[j]){
act[ind] = 1;
if(ind && act[ind - 1])
left.merge(ind - 1, ind), right.merge(ind - 1, ind);
if(ind < M - 1 && act[ind + 1])
left.merge(ind, ind + 1), right.merge(ind, ind + 1);
}
set<pair<int, int>> interval;
for(int ind : same_idx[j])
interval.insert({left.find(ind), right.find(ind)});
for(auto [tl, tr] : interval)
if(tl != 0 && tr != M - 1)
arr[i].pb({tl, tr});
}
}
return arr;
};
auto extend = [&](int N, int M, vector<vector<pair<int, int>>> & ROWS, int t){
vector<vector<vector<pair<int, int>>>> down_extend(N, vector<vector<pair<int, int>>>(M));
vector<vector<int>> dp(M, vector<int>(M, -1));
vector<vector<int>> dp2(M, vector<int>(M, -1));
for(int i = N - 1; i >= 0; i--){
for(auto [tl, tr] : ROWS[i]){
int cev = (dp[tl][tr] == i + 1 ? dp2[tl][tr] + 1 : 1);
down_extend[i][tl].pb((t ? make_pair(cev, tr) : make_pair(tr, cev)));
dp[tl][tr] = i;
dp2[tl][tr] = cev;
}
}
vector<vector<vector<pair<int, int>>>> ret(M, vector<vector<pair<int, int>>>(N));
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) ret[j][i] = down_extend[i][j];
return (t ? ret : down_extend);
};
vector<vector<int>> A(m, vector<int>(n));
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) A[j][i] = a[i][j];
auto rows = compute(n, m, a);
auto cols = compute(m, n, A);
auto down_extend = extend(n, m, rows, 0);
auto right_extend = extend(m, n, cols, 1);
fenwick fen(n);
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
sort(all(right_extend[i][j])); sort(all(down_extend[i][j])); reverse(all(down_extend[i][j]));
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int c = right_extend[i][j].size() - 1;
vector<int> rollback;
for(auto [tr, ext] : down_extend[i][j]){
while(c >= 0 && j + right_extend[i][j][c].first - 1 >= tr){
fen.upd(right_extend[i][j][c].second , 1);
rollback.pb(right_extend[i][j][c].second);
c--;
}
ans += fen.query(i, i + ext - 1);
}
for(int x : rollback)
fen.upd(x, -1);
}
}
return ans;
}
