#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
const int maxn = 2.5e3 + 5 ;
vector<pi> rightedges[maxn][maxn];//col row
vector<pi> bottomedges[maxn][maxn];//row col
const int maxval = 7e6+5;
struct SegTree{
int st[maxval * 4 + 5];
void init(){
memset(st, 0, sizeof(st));
}
void upd(int n, int l , int r, int ind, int val){
if(l == r) {
st[n] += val;
return;
}
int mid = (l + r)/2;
if( mid >= ind)
upd(2*n+1, l,mid, ind, val);
else
upd(2*n +2, mid + 1, r, ind, val);
st[n] =st[2*n+1] + st[2*n+2];
}
void insert(int val){
upd(0,1, maxval,val, 1 );
}
int qry(int n, int l, int r, int s , int e){
if(s <= l and e >= r){
// cout <<l<<", "<<r<<", "<<s<<", "<<e<<": "<<st[n]<<endl;
return st[n];
}
int mid = (l + r)/2;
int ans = 0;
if( mid >= s)
ans+= qry(2*n+ 1, l, mid, s, e);
if(mid <e)
ans+= qry(2*n+2, mid + 1, r, s,e);
return ans;
}
int query(int val){
return qry(0,1, maxval, val, maxval);
}
};
bool cmp(pi a, pi b){
return a.s == b.s ? a.f < b.f: a.s < b.s;
}
SegTree st;
long long count_rectangles(vector<vector<int> > a) {
int n = a.size();
int m = a[0].size();
for(int row = 1; row < n -1; row++){
stack<int> stck;
stck.push(0);
//the stack is always in decreasing order
//we keep track of what indices work and which ones don't
for(int col = 1; col <m ; col++){
while(stck.size()){
if(stck.top() != col -1){
rightedges[row][stck.top() +1].pb({col -1, row});
}
if(a[row][stck.top()] < a[row][col]){
//if the current cell is taller than the left edge, then no rectangles can be made
//from left past the current cell
stck.pop();
}
else {
if (a[row][stck.top()] == a[row][col]){
stck.pop();
}
break;
}
//else, left is taller than curcell
//this means that we can build more rectangles
}
stck.push(col);
}
}
/*
for(int row = 1; row < n -1; row++){
for(int col = 1; col <m ; col++){
cout << row<<", "<<col<<": ";
for(pi p : rightedges[row][col])
cout << p.second<<", "<<p.first<<";";
cout <<endl;
}
}*/
for(int col = 1; col < m -1; col++){
stack<int> stck;
stck.push(0);
//the stack is always in decreasing order
//we keep track of what indices work and which ones don't
for(int row = 1; row <n ; row++){
while(stck.size()){
if(stck.top() != row -1){
bottomedges[stck.top() +1][col].pb({row - 1, col});
}
if(a[stck.top()][col] < a[row][col]){
//if the current cell is taller than the left edge, then no rectangles can be made
//from left past the current cell
stck.pop();
}
else {
if (a[stck.top()][col] == a[row][col]){
stck.pop();
}
break;
}
//else, left is taller than curcell
//this means that we can build more rectangles
}
stck.push(row);
}
}
/*for(int row = 1; row < n; row++){
for(int col = 1; col <m -1; col++){
cout << row<<", "<<col<<": ";
for(pi p : bottomedges[row][col])
cout << p.first<<", "<<p.second<<";";
cout <<endl;
}
}*/
for(int row = n -2; row >0; row--){
for(int col = m-2; col >0; col--){
//int row_size
for(int i =0; i<rightedges[row][col].size(); i++){
auto it = lower_bound(rightedges[row+1][col].begin(), rightedges[row+1][col].end(),mp(rightedges[row][col][i].f, -1));
if(it != rightedges[row + 1][col].end() and it->f == rightedges[row][col][i].f)
rightedges[row][col][i].s = it ->s;
}
for(int i =0; i<bottomedges[row][col].size(); i++){
auto it = lower_bound(bottomedges[row][col+1].begin(), bottomedges[row][col+1].end(),mp(bottomedges[row][col][i].f, -1));
if(it != bottomedges[row][col+1].end() and it->f == bottomedges[row][col][i].f)
bottomedges[row][col][i].s = it ->s;
}
}
}
ll ans = 0;
for(int row = 1; row< n -1; row++){
for(int col = 1; col < m-1; col++){
sort(rightedges[row][col].begin(), rightedges[row][col].end(), cmp);//sort by second
sort(bottomedges[row][col].begin(), bottomedges[row][col].end());//sort by first
int rpntr = 0;
int bpntr = 0;
int rsz = rightedges[row][col].size();
int bsz = bottomedges[row][col].size();
st.init();
int cnt = 0;
while(rpntr < rsz){
int cntr = 0;
while(bpntr < bsz and rightedges[row][col][rpntr].s >= bottomedges[row][col][bpntr].f){
st.insert(bottomedges[row][col][bpntr].s + 1);
//if(row == 1 and col == 1)
//cout << bottomedges[row][col][bpntr].f <<", "<<bottomedges[row][col][bpntr].s<<endl;
bpntr++;
cntr++;
if(cntr >= 10000) {
cout <<"bad2\n";exit(0);
}
}
ans += st.query(rightedges[row][col][rpntr].f +1);//number currently greater than thi
/*if(row == 1 and col == 1){
cout << rightedges[row][col][rpntr].s <<"; "<<rightedges[row][col][rpntr].f<<endl;
cout <<rightedges[row][col][rpntr].f <<": "<< st.query(rightedges[row][col][rpntr].f +1)<<endl;
}*/
rpntr++;
cnt++;
if(cnt >= 10000) {
cout <<"bad1\n";exit(0);
}
}
/*for(int r = 0; r < rightedges[row][col].size(); r++){
for(int c =bottomedges[row][col].size() -1 ; c>=0 ; c--){
if(row == 1 and col == 1){
cout << rightedges[row][col][r].s<<", "<<rightedges[row][col][r].f<<":::";
cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
}
if(rightedges[row][col][r].f <= bottomedges[row][col][c].s){
if(rightedges[row][col][r].s >= bottomedges[row][col][c].f){
ans++;
//cout << row<<", "<<col<<": ";
//cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
}
}
}
}*/
}
}
return ans;
}
/**************/
