/**
* 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;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int ll
const char nl = '\n';
const int N = 1e6+10;
vector<int> r, c;
int h, w, p[N];
struct segtree {
vector<tuple<int, int, int, int>> tree; // rmin, rmax, cmin, cmax.
int size, hh;
void init(int n) {
size = 1, hh = n;
while (size < n)size <<= 1;
tree.assign(2*size-1, {hh, 0, hh, 0});
}
tuple<int, int, int, int> combine(tuple<int, int, int, int>a, tuple<int, int, int, int>b) {
int q, ww, e, rr;
tie(q, ww, e, rr) = a;
int q1, w1, e1, r1;
tie(q1, w1, e1, r1) = b;
return {min(q, q1), max(ww, w1), min(e, e1), max(rr, r1)};
}
void build(vector<int> &rr, vector<int> &cc, int x, int lx, int rx) {
if (rx-lx == 1) {
if (lx < sz(r))
tree[x] = {rr[lx], rr[lx], cc[lx], cc[lx]};
return;
}
int mid = lx+rx>>1;
build(rr, cc, 2*x+1, lx, mid);
build(rr, cc, 2*x+2, mid, rx);
tree[x] = combine(tree[2*x+1], tree[2*x+2]);
}
void build(vector<int> &rr, vector<int> &cc) {
init(sz(rr));
build(rr, cc, 0, 0, size);
}
//void set(int i, int u, int v) {
//}
void set(int i, int u, int v) {
int x = size+i-1;
tree[x] = {u, u, v, v};
while (x > 0) {
x = (x-1)/2;
tree[x] = combine(tree[2*x+1], tree[2*x+2]);
}
}
tuple<int, int, int, int> get(int l, int rr, int x, int lx, int rx) {
if (rx <= l || rr <= lx)return {hh, 0, hh, 0};
if (lx >= l && rx <= rr)return tree[x];
int mid = lx+rx>>1;
return combine(get(l, rr, 2*x+1, lx, mid), get(l, rr, 2*x+2, mid, rx));
}
tuple<int, int, int, int> get(int l, int rr) {
return get(l, rr, 0, 0, size);
}
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;
}
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}, tree[2*x+1])) {
ok = false;
return fnd(m1, m2, m3, m4, 2*x+1, lx, mid);
} else {
if (!lezit({m1, m2, m3, m4}, tree[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, size);
}
};
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.build(r, c);
//st.set(1, r[0], c[0]);
//for (int i = 0; i < h*w; ++i) {
//auto yu = st.get(0, i+1);
//int x, y, z, d;
//tie(x, y, z, d) = yu;
//g[i] = (x-y+1)*(z-d+1);
//}
}
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);
int ans = 0;
while (i < h*w) {
int lx = st.fnd(m1, m2, m3, m4);
if (g - (lx-1)-1 == 0)
ans += 1;
i = lx;
tie(m1, m2, m3, m4) = st.get(0, lx+1);
g = (m2-m1+1)*(m4-m3+1);
}
return ans+1;
}
//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;
//}
