#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
struct Node {
int r1, r2, c1, c2;
Node() : r1(INT_MAX), r2(INT_MIN), c1(INT_MAX), c2(INT_MIN) {}
Node(int r, int c) {
r1 = r2 = r; c1 = c2 = c;
}
Node(Node left, Node right) {
r1 = min(left.r1, right.r1); r2 = max(left.r2, right.r2);
c1 = min(left.c1, right.c1); c2 = max(left.c2, right.c2);
}
int area() {
return (r2 - r1 + 1) * (c2 - c1 + 1);
}
};
struct SegTree {
int n; vi row, col; vector<Node> st;
SegTree() {};
SegTree(int N, vi &R, vi &C) {
n = N; row = R; col = C; st.resize(4*n);
build(0, 0, n);
}
Node build(int i, int l, int r) {
if (l+1 == r) return st[i] = Node(row[l], col[l]);
int m = l + (r - l) / 2;
return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
}
Node query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return Node();
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
Node update(int i, int l, int r, int k, int x, int y) {
if (!(l <= k && k < r)) return st[i];
if (l+1 == r) {
row[k] = x; col[k] = y;
return st[i] = Node(x, y);
}
int m = l + (r - l) / 2;
return st[i] = Node(update(2*i+1, l, m, k, x, y), update(2*i+2, m, r, k, x, y));
}
};
int n, h, w;
vi r, c;
SegTree st;
void give_initial_chart(int H, int W, vi R, vi C) {
h = H, w = W, n = h*w;
r = R, c = C;
st = SegTree(n, r, c);
}
int swap_seats(int a, int b) {
swap(r[a], r[b]); swap(c[a], c[b]);
st.update(0, 0, n, a, r[a], c[a]);
st.update(0, 0, n, b, r[b], c[b]);
int t = 0;
for (int i = 0; i < n; i++) {
auto R = st.query(0, 0, n, 0, i+1);
if (R.area() == i+1) t++;
else i = R.area() - 2;
}
return t;
}
