#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
struct SegTree {
int n; vi arr; vpi st;
SegTree() {};
SegTree(int N, vi &Arr) {
n = N; arr = Arr; st.assign(4*n, {INT_MIN, INT_MAX});
build(0, 0, n);
}
pi combine(pi left, pi right) {
return {max(left.first, right.first), min(left.second, right.second)};
}
pi build(int i, int l, int r) {
if (l+1 == r) return st[i] = {arr[l], arr[l]};
int m = l + (r - l) / 2;
return st[i] = combine(build(2*i+1, l, m), build(2*i+2, m, r));
}
pi query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return {INT_MIN, INT_MAX};
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return combine(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
pi update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l+1 == r) {
arr[k] = v;
return st[i] = {arr[k], arr[k]};
}
int m = l + (r - l) / 2;
return st[i] = combine(update(2*i+1, l, m, k, v), update(2*i+2, m, r, k, v));
}
};
int h, w;
vi r, c;
SegTree rows, cols;
void give_initial_chart(int H, int W, vi R, vi C) {
h = H, w = W;
r = R, c = C;
rows = SegTree(h*w, r), cols = SegTree(h*w, c);
}
int garea(pi R, pi C) {
return (R.first-R.second + 1) * (C.first-C.second + 1);
}
int swap_seats(int a, int b) {
swap(r[a], r[b]); swap(c[a], c[b]);
rows.update(0, 0, h*w, a, r[a]), rows.update(0, 0, h*w, b, r[b]);
cols.update(0, 0, h*w, a, c[a]), cols.update(0, 0, h*w, b, c[b]);
int t = 0;
for (int i = 0; i < h*w; i++) {
pi R = rows.query(0, 0, h*w, 0, i+1), C = cols.query(0, 0, h*w, 0, i+1);
if (garea(R, C) == i+1) t++;
else i = garea(R, C) - 2;
}
return t;
}
