#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;
int minX(int x) {
return l.query(0, x);
}
int maxX(int x) {
return r.query(0, x);
}
int minY(int x) {
return u.query(0, x);
}
int maxY(int x) {
return d.query(0, x);
}
int good(int sz, pair<int, int> xbound, pair<int, int> ybound) {
return ((xbound.second - xbound.first + 1) *
(ybound.second - ybound.first + 1)) == sz;
}
int ans() {
int answ = 0;
int lx = l.query(0);
int rx = r.query(0);
int uy = u.query(0);
int dy = d.query(0);
pair<int, int> xbound = {lx, rx};
pair<int, int> ybound = {uy, dy};
int lst = -1;
while (true) {
int sz = (xbound.second - xbound.first + 1) *
(ybound.second - ybound.first + 1);
assert(sz != lst);
if (good(sz, xbound, ybound)) {
answ++;
}
if (sz == h * w) break;
lx = minX(sz);
rx = maxX(sz);
uy = minY(sz);
dy = maxY(sz);
xbound = {lx, rx};
ybound = {uy, dy};
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();
}
