#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#include <random>
#include <set>
#include <unordered_set>

struct Hash {
    size_t operator()(uint32_t a) const {
        return (a * 1ULL * a + 228ULL * a + 336) % uint32_t(1e9 + 7);
    }
};

template <typename T>
using hash_set =
    __gnu_pbds::gp_hash_table<T,
                              __gnu_pbds::null_type,
                              Hash,
                              std::equal_to<T>>;

std::vector<std::pair<int, int>> get_cum(const std::vector<int>& vec) {
    int n = vec.size();
    std::vector<int> stack;
    std::vector<std::pair<int, int>> res;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && vec[stack.back()] <= vec[i]) {
            if (stack.size() > 1 && vec[stack.back()] < vec[i]) {
                res.push_back({stack.rbegin()[1] + 1, i - 1});
            }
            stack.pop_back();
        }
        stack.push_back(i);
    }
    std::sort(res.begin(), res.end());
    return res;
}

uint32_t hash(const std::pair<int, int> p) {
    return (p.first << 16) + p.second;
}

long long count_rectangles(std::vector<std::vector<int>> a) {
    std::mt19937 rnd;

    int n = a.size();
    int m = a[0].size();
    std::vector<std::vector<int>> t_a(m, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            t_a[j][i] = a[i][j];
        }
    }

    std::vector<std::vector<std::pair<int, int>>> rw(n), cl(m);
    std::vector<hash_set<uint32_t>> s_rw(n), s_cl(m);
    for (int i = 0; i < n; i++) {
        rw[i] = get_cum(a[i]);
        for (auto& p : rw[i]) {
            s_rw[i].insert(hash(p));
        }
    }
    for (int i = 0; i < m; i++) {
        cl[i] = get_cum(t_a[i]);
        for (auto& p : cl[i]) {
            s_cl[i].insert(hash(p));
        }
    }

    int ans = 0;

    auto fuck = [&](auto fuck, int beg, int end) -> void {
        if (beg >= end) {
            return;
        }
        int md = (beg + end) / 2;
        for (auto& [l1, r1] : rw[md]) {
            int bd1 = md, bd2 = md;
            while (bd1 > beg) {
                if (s_rw[bd1 - 1].find(hash({l1, r1})) == s_rw[bd1 - 1].end()) {
                    break;
                }
                bd1--;
            }
            while (bd2 + 1 < end) {
                if (s_rw[bd2 + 1].find(hash({l1, r1})) == s_rw[bd2 + 1].end()) {
                    break;
                }
                bd2++;
            }

            std::vector<int> ord;
            for (int i = l1 + 1; i < r1; i++) {
                ord.push_back(i);
            }
            std::shuffle(ord.begin(), ord.end(), rnd);

            for (auto [l2, r2] : get_cum(std::vector<int>(t_a[l1].begin() + bd1 - 1, t_a[l1].begin() + bd2 + 2))) {
                // for (auto [l2, r2] : cl[l1]) {
                l2 += bd1 - 1;
                r2 += bd1 - 1;

                if (!(l2 <= md && md <= r2 && bd1 <= l2 && r2 <= bd2)) {
                    continue;
                }
                bool fck = false;

                // for (int i = l1 + 1; i <= r1; i++) {
                for (int it = 0; it < ord.size(); it++) {
                    int i = ord[it];
                    if (ord.size() > 40 && it > 20) {
                        continue;
                    }
                    if (s_cl[i].find(hash({l2, r2})) == s_cl[i].end()) {
                        fck = true;
                        break;
                    }
                }
                if (!fck) {
                    ans++;

                    // if (ans % 1000 == 0)
                    //     std::cerr << l2 << " " << r2 << "  " << l1 << " " << r1 << "  |" << beg << ", " << end << "  md: " << md << "\n";
                }
            }
        }
        if (beg + 1 < end) {
            fuck(fuck, beg, md);
            fuck(fuck, md + 1, end);
        }
    };
    fuck(fuck, 1, n - 1);

    return ans;
}

implementer.cpp:22:34: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   22 | inline void freadn(register int *Q) {
      |                                  ^
implementer.cpp:27:37: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   27 | inline void freadstr(register char *s) {
      |                                     ^
implementer.cpp: In function ‘void readinp()’:
implementer.cpp:19:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |         fread(ptr, 0x1, inSize, stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:63,
                 from rect.h:1,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~