#include "seats.h"
#include <bits/stdc++.h>
namespace SOLVE {
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
constexpr int infty = 1e9;
template<class M>
class SegmentTree {
using T = typename M::T;
int n, ori;
vector<T> dat;
public:
void init(int n_) {
ori = n_;
n = 1;
while (n < n_) n *= 2;
dat.assign(2 * n, M::id());
}
void set(int k, T x) {
k += n;
dat[k] = x;
while (k > 1) {
k /= 2;
dat[k] = M::op(dat[k * 2], dat[k * 2 + 1]);
}
}
T prod(int l, int r) const {
T sml = M::id(), smr = M::id();
l += n; r += n;
while (l < r) {
if (l & 1) sml = M::op(sml, dat[l++]);
if (r & 1) smr = M::op(dat[--r], smr);
l >>= 1; r >>= 1;
}
return M::op(sml, smr);
}
template<class F>
int max_right(int k, F&& f) const {
if (k == ori) return ori;
k += n;
T sm = M::id();
do {
while (k % 2 == 0) k >>= 1;
if (!f(M::op(sm, dat[k]))) {
while (k < n) {
k = 2 * k;
if (f(M::op(sm, dat[k]))) {
sm = M::op(sm, dat[k]);
++k;
}
}
return k - n;
}
sm = M::op(sm, dat[k]);
++k;
} while ((k & -k) != k);
return ori;
}
};
struct Max {
using T = int;
static T id() { return -infty; }
static T op(T a, T b) { return max(a, b); }
};
struct Min {
using T = int;
static T id() { return infty; }
static T op(T a, T b) { return min(a, b); }
};
int H, W;
vector<int> R, C;
SegmentTree<Min> mR, mC;
SegmentTree<Max> MR, MC;
}
void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
using namespace SOLVE;
H = H_; W = W_;
R = R_; C = C_;
mR.init(H * W);
MR.init(H * W);
mC.init(H * W);
MC.init(H * W);
rep (i, H * W) {
mR.set(i, R[i]);
MR.set(i, R[i]);
mC.set(i, C[i]);
MC.set(i, C[i]);
}
}
int swap_seats(int a, int b) {
using namespace SOLVE;
if (a > b) swap(a, b);
swap(R[a], R[b]);
swap(C[a], C[b]);
mR.set(a, R[a]); mR.set(b, R[b]);
MR.set(a, R[a]); MR.set(b, R[b]);
mC.set(a, C[a]); mC.set(b, C[b]);
MC.set(a, C[a]); MC.set(b, C[b]);
int mr = R[0], Mr = R[0];
int mc = C[0], Mc = C[0];
int ans = 1;
while (mr > 0 || Mr < H - 1 || mc > 0 || Mc < W - 1) {
int nxt = min({
mR.max_right(0, [&](int x) { return x >= mr; }),
MR.max_right(0, [&](int x) { return x <= Mr; }),
mC.max_right(0, [&](int x) { return x >= mc; }),
MC.max_right(0, [&](int x) { return x <= Mc; })
});
if (nxt == (Mr - mr + 1) * (Mc - mc + 1)) ++ans;
chmin(mr, R[nxt]);
chmax(Mr, R[nxt]);
chmin(mc, C[nxt]);
chmax(Mc, C[nxt]);
}
return ans;
}
