#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class Segmin {
private:
int n;
vector<int> a;
vector<multiset<int>> bit;
void add(int idx, int val) {
for (++idx; idx <= n; idx += idx & -idx) {
bit[idx].insert(val);
}
}
void remove_val(int idx, int val) {
for (++idx; idx <= n; idx += idx & -idx) {
auto it = bit[idx].find(val);
if (it != bit[idx].end()) bit[idx].erase(it);
}
}
public:
Segmin() {
n = 0;
}
Segmin(vector<int> b) {
n = (int)b.size();
a = b;
bit.assign(n + 1, {});
build();
}
void build() {
bit.assign(n + 1, {});
for (int i = 0; i < n; i++) add(i, a[i]);
}
int query(int l, int r) {
assert(l == 0);
int res = 1e8;
for (++r; r > 0; r -= r & -r) {
if (!bit[r].empty()) res = min(res, *bit[r].begin());
}
return res;
}
int query(int i) {
return a[i];
}
void upd(int qi, int qv) {
remove_val(qi, a[qi]);
a[qi] = qv;
add(qi, qv);
}
};
class Segmax {
private:
int n;
vector<int> a;
vector<multiset<int>> bit;
void add(int idx, int val) {
for (++idx; idx <= n; idx += idx & -idx) {
bit[idx].insert(val);
}
}
void remove_val(int idx, int val) {
for (++idx; idx <= n; idx += idx & -idx) {
auto it = bit[idx].find(val);
if (it != bit[idx].end()) bit[idx].erase(it);
}
}
public:
Segmax() {
n = 0;
}
Segmax(vector<int> b) {
n = (int)b.size();
a = b;
bit.assign(n + 1, {});
build();
}
void build() {
bit.assign(n + 1, {});
for (int i = 0; i < n; i++) add(i, a[i]);
}
int query(int l, int r) {
assert(l == 0);
int res = -1e8;
for (++r; r > 0; r -= r & -r) {
if (!bit[r].empty()) res = max(res, *bit[r].rbegin());
}
return res;
}
int query(int i) {
return a[i];
}
void upd(int qi, int qv) {
remove_val(qi, a[qi]);
a[qi] = qv;
add(qi, qv);
}
};
Segmin l, u;
Segmax r, d;
vector<int> X, Y;
int h, w;
const int MX = 1000005;
int cache_ver = 0;
int seen_minX[MX], seen_maxX[MX], seen_minY[MX], seen_maxY[MX];
int cache_minX[MX], cache_maxX[MX], cache_minY[MX], cache_maxY[MX];
int minX(int x) {
if (seen_minX[x] != cache_ver) {
seen_minX[x] = cache_ver;
cache_minX[x] = l.query(0, x);
}
return cache_minX[x];
}
int maxX(int x) {
if (seen_maxX[x] != cache_ver) {
seen_maxX[x] = cache_ver;
cache_maxX[x] = r.query(0, x);
}
return cache_maxX[x];
}
int minY(int x) {
if (seen_minY[x] != cache_ver) {
seen_minY[x] = cache_ver;
cache_minY[x] = u.query(0, x);
}
return cache_minY[x];
}
int maxY(int x) {
if (seen_maxY[x] != cache_ver) {
seen_maxY[x] = cache_ver;
cache_maxY[x] = d.query(0, x);
}
return cache_maxY[x];
}
int good(int sz) {
return ((maxX(sz - 1) - minX(sz - 1) + 1) *
(maxY(sz - 1) - minY(sz - 1) + 1)) == sz;
pair<int, int> xb = {minX(sz - 1), maxX(sz - 1)};
pair<int, int> yb = {minY(sz - 1), maxY(sz - 1)};
pair<int, int> xba = {min(l.query(0), l.query(sz - 1)), max(r.query(0), r.query(sz - 1))};
pair<int, int> yba = {min(u.query(0), u.query(sz - 1)), max(d.query(0), d.query(sz - 1))};
return (xb == xba && yb == yba);
}
int ans() {
cache_ver++;
int answ = 0;
pair<int, int> xbound = {l.query(0), r.query(0)};
pair<int, int> ybound = {u.query(0), d.query(0)};
int lst = -1;
while (true) {
int sz = (xbound.second - xbound.first + 1) *
(ybound.second - ybound.first + 1);
assert(sz != lst);
if (good(sz)) {
answ++;
}
if (sz == h * w) break;
xbound = {minX(sz), maxX(sz)};
ybound = {minY(sz), maxY(sz)};
lst = sz;
}
return answ;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
X.resize(H * W);
Y.resize(H * W);
h = H;
w = W;
for (int i = 0; i < H * W; i++) {
X[i] = C[i];
Y[i] = R[i];
}
l = Segmin(X);
r = Segmax(X);
u = Segmin(Y);
d = Segmax(Y);
}
int swap_seats(int a, int b) {
int oldxa = X[a];
l.upd(a, X[b]);
r.upd(a, X[b]);
l.upd(b, oldxa);
r.upd(b, oldxa);
int oldya = Y[a];
u.upd(a, Y[b]);
d.upd(a, Y[b]);
u.upd(b, oldya);
d.upd(b, oldya);
swap(X[a], X[b]);
swap(Y[a], Y[b]);
return ans();
}
