#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class Segmin {
private:
int n;
vector<int> a, seg;
void build(int i, int l, int r) {
if (l > r) return;
if (l == r) {
seg[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
}
int query(int i, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 1e8;
if (ql <= l && r <= qr) return seg[i];
int mid = (l + r) / 2;
return min(query(i * 2, l, mid, ql, qr), query(i * 2 + 1, mid + 1, r, ql, qr));
}
void upd(int i, int l, int r, int qi, int qv) {
if (l == r) {
seg[i] = a[l] = qv;
return;
}
int mid = (l + r) / 2;
if (qi <= mid) upd(i * 2, l, mid, qi, qv);
else upd(i * 2 + 1, mid + 1, r, qi, qv);
seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
}
public:
Segmin(vector<int> b) {
n = (int)b.size();
a = b; seg.resize(4 * n);
build(1, 0, n - 1);
}
void build() { build(1, 0, n - 1); }
int query(int l, int r) { return query(1, 0, n - 1, l, r); }
int query(int i) { return query(1, 0, n - 1, i, i); }
void upd(int qi, int qv) { upd(1, 0, n - 1, qi, qv); }
};
class Segmax {
private:
int n;
vector<int> a, seg;
void build(int i, int l, int r) {
if (l > r) return;
if (l == r) {
seg[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
int query(int i, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return -1e8;
if (ql <= l && r <= qr) return seg[i];
int mid = (l + r) / 2;
return max(query(i * 2, l, mid, ql, qr), query(i * 2 + 1, mid + 1, r, ql, qr));
}
void upd(int i, int l, int r, int qi, int qv) {
if (l == r) {
seg[i] = a[l] = qv;
return;
}
int mid = (l + r) / 2;
if (qi <= mid) upd(i * 2, l, mid, qi, qv);
else upd(i * 2 + 1, mid + 1, r, qi, qv);
seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
public:
Segmax(vector<int> b) {
n = (int)b.size();
a = b; seg.resize(4 * n);
build(1, 0, n - 1);
}
void build() { build(1, 0, n - 1); }
int query(int l, int r) { return query(1, 0, n - 1, l, r); }
int query(int i) { return query(1, 0, n - 1, i, i); }
void upd(int qi, int qv) { upd(1, 0, n - 1, 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;
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))};
// cout << "checking size\n";
// cout << "xb:\n";
// cout << xb.first << " " << xb.second << '\n';
// cout << "xba:\n";
// cout << xba.first << " " << xba.second << '\n';
// cout << "yb:\n";
// cout << yb.first << " " << yb.second << '\n';
// cout << "yba:\n";
// cout << yba.first << " " << yba.second << '\n';
return (xb == xba && yb == yba);
}
int ans() {
// cout << "finding ans\n";
int answ = 0;
pair<int, int> xbound = {l.query(0), l.query(0)};
pair<int, int> ybound = {u.query(0), d.query(0)};
// cout << "X:\n";
// for (int i = 0; i < h*w; i++) cout << l.query(i) << " ";
// cout << '\n';
// cout << "Y:\n";
// for (int i = 0; i < h*w; i++) cout << d.query(i) << " ";
// cout << '\n';
int lst = -1;
while (true) {
// is this good?
int sz = (xbound.second-xbound.first+1)*(ybound.second-ybound.first+1);
assert(sz != lst);
// cout << sz << " size\n";
// cout << xbound.first+1 << " -> " << xbound.second+1 << '\n';
// cout << ybound.first+1 << " -> " << ybound.second+1 << '\n';
if (good(sz)) {
// cout << "yezzir\n";
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);
// cout << "done initial\n";
}
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]);
// cout << "done swap\n";
return ans();
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
