#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class Segmin {
private:
int n;
vector<short> seg;
public:
Segmin() {
n = 0;
}
Segmin(vector<short> b) {
n = (int)b.size();
seg.assign(2 * n, 32767);
for (int i = 0; i < n; i++) {
seg[n + i] = b[i];
}
build();
}
void build() {
for (int i = n - 1; i > 0; i--) {
seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
}
}
int query(int l, int r) {
int res = 32767;
for (l += n, r += n; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) res = min(res, (int)seg[l++]);
if (r % 2 == 0) res = min(res, (int)seg[r--]);
}
return res;
}
int query(int i) {
return seg[n + i];
}
void upd(int qi, int qv) {
int p = qi + n;
seg[p] = (short)qv;
for (p /= 2; p > 0; p /= 2) {
seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
}
}
};
class Segmax {
private:
int n;
vector<short> seg;
public:
Segmax() {
n = 0;
}
Segmax(vector<short> b) {
n = (int)b.size();
seg.assign(2 * n, -32768);
for (int i = 0; i < n; i++) {
seg[n + i] = b[i];
}
build();
}
void build() {
for (int i = n - 1; i > 0; i--) {
seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
}
int query(int l, int r) {
int res = -32768;
for (l += n, r += n; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) res = max(res, (int)seg[l++]);
if (r % 2 == 0) res = max(res, (int)seg[r--]);
}
return res;
}
int query(int i) {
return seg[n + i];
}
void upd(int qi, int qv) {
int p = qi + n;
seg[p] = (short)qv;
for (p /= 2; p > 0; p /= 2) {
seg[p] = max(seg[p * 2], seg[p * 2 + 1]);
}
}
};
Segmin l, u;
Segmax r, d;
vector<short> 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];
short 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] = (short)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] = (short)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] = (short)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] = (short)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] = (short)C[i];
Y[i] = (short)R[i];
}
l = Segmin(X);
r = Segmax(X);
u = Segmin(Y);
d = Segmax(Y);
}
int swap_seats(int a, int b) {
short oldxa = X[a];
l.upd(a, X[b]);
r.upd(a, X[b]);
l.upd(b, oldxa);
r.upd(b, oldxa);
short 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();
}
