/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;
//bool f(int l, int r) {
//}
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int ll
const char nl = '\n';
vector<int> r, c;
short int h, w;
struct segtree {
int n;
vector<short int> rmin, rmax, cmin, cmax;
void init(int size) {
n = 1;
while (n < size) n <<= 1;
rmin.assign(2 * n-1, size);
rmax.assign(2 * n-1, 0);
cmin.assign(2 * n-1, size);
cmax.assign(2 * n-1, 0);
}
void build(vector<int> &rr, vector<int> &cc, int x, int lx, int rx) {
if (rx-lx == 1) {
if (lx < sz(rr))
rmin[x] = rmax[x] = rr[lx],
cmin[x] = cmax[x] = cc[lx];
return;
}
int mid = lx+rx>>1;
build(rr, cc, 2*x+1, lx, mid);
build(rr, cc, 2*x+2, mid, rx);
rmin[x] = min(rmin[2*x+1], rmin[2*x+2]);
cmin[x] = min(cmin[2*x+1], cmin[2*x+2]);
rmax[x] = max(rmax[2*x+1], rmax[2*x+2]);
cmax[x] = max(cmax[2*x+1], cmax[2*x+2]);
}
void build(vector<int> &rr, vector<int> &cc) {
build(rr, cc, 0, 0, n);
}
void set(int i, int rr, int cc) {
i = i+n-1;
rmin[i] = rmax[i] = rr;
cmin[i] = cmax[i] = cc;
while (i > 0) {
i = (i-1)/2;
rmin[i] = min(rmin[2*i+1], rmin[2*i+2]);
cmin[i] = min(cmin[2*i+1], cmin[2*i+2]);
rmax[i] = max(rmax[2*i+1], rmax[2*i+2]);
cmax[i] = max(cmax[2*i+1], cmax[2*i+2]);
}
}
bool lezit(tuple<int, int, int, int> a, tuple<int, int, int, int> b) {
int x, y, z, q;
tie(x, y, z, q) = a;
int m1, m2, m3, m4;
tie(m1, m2, m3, m4) = b;
if (m1 >= x && m1 <= y && m2 >= x && m2 <= y)
if (m3 >= z && m3 <= q && m4 >= z && m4 <= q)return true;
return false;
}
tuple<int, int, int, int> get(int l, int rr, int x, int lx, int rx) {
if (rx <= l || rr <= lx)return {INT_MAX, INT_MIN, INT_MAX, INT_MIN};
if (lx >= l && rx <= rr)return {rmin[x], rmax[x], cmin[x], cmax[x]};
int mid = lx+rx>>1;
int a, b, cc, d;
tie(a, b, cc, d) = get(l, rr, 2*x+1, lx, mid);
int xx, y, z, dd;
tie(xx, y, z, dd) = get(l, rr, 2*x+2, mid, rx);
return {min(a, xx), max(b, y), min(cc, z), max(d, dd)};
}
tuple<int, int, int, int> get(int l, int rr) {
return get(l, rr, 0, 0, n);
}
int fnd(int m1, int m2, int m3, int m4, int x, int lx, int rx) {
if (rx-lx==1) {
return rx-1;
}
int mid = (lx + rx >> 1);
bool ok = true;
if (!lezit({m1, m2, m3, m4}, {rmin[2*x+1], rmax[2*x+1], cmin[2*x+1], cmax[2*x+1]})) {
ok = false;
return fnd(m1, m2, m3, m4, 2*x+1, lx, mid);
} else {
if (!lezit({m1, m2, m3, m4}, {rmin[2*x+2], rmax[2*x+2], cmin[2*x+2], cmax[2*x+2]})) {
ok = false;
return fnd(m1, m2, m3, m4, 2*x+2, mid, rx);
}
}
if (ok) {
return rx-1;
}
}
int fnd(int m1, int m2, int m3, int m4) {
return fnd(m1, m2, m3, m4, 0, 0, n);
}
};
segtree st;
//int g[N];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R, c = C;
h = H, w = W;
st.init(h * w);
st.build(r, c);
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
st.set(a, r[a], c[a]);
st.set(b, r[b], c[b]);
int i = 0;
//int x, y, z, d;
int m1, m2, m3, m4;
tie(m1, m2, m3, m4) = {r[0], r[0], c[0], c[0]};
int g = (m2-m1+1)*(m4-m3+1);
short int ans = 0;
while (i < h*w) {
if (i+1 == g) {
ans += 1, i += 1;
} else
i = g-1;
tie(m1, m2, m3, m4) = st.get(0, i+1);
g = (m2-m1+1)*(m4-m3+1);
}
return ans;
}
//void solve() {
//int H, W, Q;
//cin >> H >> W >> Q;
//vector<int> R, C;
//R.resize(H*W); C.resize(H*W);
//for (int i = 0; i < H*W; ++i)cin >> R[i] >> C[i];
//give_initial_chart(H, W, R, C);
//while (Q--) {
//int a, b; cin >> a >> b;
//cout << swap_seats(a, b) << nl;
//}
//}
//int32_t main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//int t = 1;
//for (int _ = 0; _ < t; ++_) {
//solve();
//}
//return 0;
//}
