#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(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) {
// Only prefix queries are supported efficiently.
// Your code only uses query(0, x).
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(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) {
// Only prefix queries are supported efficiently.
// Your code only uses query(0, x).
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) {
return ((maxX(sz - 1) - minX(sz - 1) + 1) *
(maxY(sz - 1) - minY(sz - 1) + 1)) == sz;
}
int ans() {
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, vector<int> R, 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();
}
