#include<bits/stdc++.h> #include "rect.h" using namespace std; #define ll long long #define L(i,j,k) for(int i=(j);i<=(k);i++) #define R(i,j,k) for(int i=(j);i>=(k);i--) #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() const int MX=2500; int bt[MX]; void upd(int id, int val){ if(id<=0)return; while(id<MX){ bt[id]+=val; id+=id&(-id); } } int query(int id){ int resp=0; if(id<=0)return 0; while(id>0){ resp+=bt[id]; id-=id&(-id); } return resp; } long long count_rectangles(std::vector<std::vector<int> > vec) { int n=sz(vec); int m=sz(vec[0]); vector<vector<vector<pair<int,int>>>> line(n,vector<vector<pair<int,int>>>(m));//so pra direita vector<vector<vector<pair<int,int>>>> col(n,vector<vector<pair<int,int>>>(m));//so pra baixo L(i,1,n-2){//calc pra baixo na col i vector<int> st; L(j,0,m-1){ while(!st.empty() && vec[i][st.back()]<=vec[i][j]){ if(st.back()+1!=j)col[i][st.back()].push_back({j,i}); st.pop_back(); } if(!st.empty()){ if(st.back()+1!=j)col[i][st.back()].push_back({j,i}); } st.push_back(j); } } L(j,1,m-2){ vector<int> st; L(i,0,n-1){ while(!st.empty() && vec[st.back()][j]<=vec[i][j]){ if(st.back()+1!=i)line[st.back()][j].push_back({i,j}); st.pop_back(); } if(!st.empty()){ if(st.back()+1!=i)line[st.back()][j].push_back({i,j}); } st.push_back(i); } } R(i,n-2,1){ L(j,0,m-1){ for(auto &[h,id]:col[i][j]){ auto pt=lower_bound(all(col[i+1][j]),make_pair(h,-1)); if(pt==col[i+1][j].end() || (*pt).first!=h)continue; id=(*pt).second; } } } R(j,m-2,1){ L(i,0,n-1){ for(auto &[c,id]:line[i][j]){ auto pt=lower_bound(all(line[i][j+1]),make_pair(c,-1)); if(pt==line[i][j+1].end() || (*pt).first!=c)continue; id=(*pt).second; } } } ll resp=0; L(i,0,n-3){ L(j,0,m-3){ vector<pair<int,int>>& C=col[i+1][j]; vector<pair<int,int>>& H=line[i][j+1]; if(C.empty() || H.empty())continue; for(auto &p:H)swap(p.first,p.second); sort(all(H)); int ptb=0; for(auto [h,longe]:C){ while(ptb<sz(H) && H[ptb].first<h-1){ resp+=query(MX-1)-query(H[ptb].second-2); ptb++; } upd(longe,1); } while(ptb<sz(H)){ resp+=query(MX-1)-query(H[ptb].second-2); ptb++; } for(auto [h,longe]:C){ upd(longe,-1); } } } return resp; }