#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
// H, W <= 1000
const int INF = 1001;
struct SGT {
int sz, null_val;
function<int(int, int)> merge;
vector<int> t;
SGT(int _sz, int _null_val, function<int(int, int)> _merge) : sz(_sz), null_val(_null_val), merge(_merge) {
t.resize(4 * sz, null_val);
}
void update(int v, int l, int r, int i, int x) {
if (l == r) t[v] = x;
else {
int mid = (l + r) / 2;
if (i <= mid) update(2 * v, l, mid, i, x);
else update(2 * v + 1, mid + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
void update(int i, int x) { update(1, 0, sz - 1, i, x); }
int query(int v, int l, int r, int L, int R) {
if (r < L or R < l) return null_val;
else if (L <= l and r <= R) return t[v];
else {
int mid = (l + r) / 2;
return merge(query(2 * v, l, mid, L, R), query(2 * v + 1, mid + 1, r, L, R));
}
}
int query(int l, int r) { return query(1, 0, sz - 1, l, r); }
};
int n, h, w;
vector<int> r, c;
SGT *row_min, *row_max, *col_min, *col_max;
void updateAllSGT(int i, int r, int c) {
row_min->update(i, r);
row_max->update(i, r);
col_min->update(i, c);
col_max->update(i, c);
}
int area(int i) {
int w_cur = row_max->query(0, i) - row_min->query(0, i) + 1;
int h_cur = col_max->query(0, i) - col_min->query(0, i) + 1;
return w_cur * h_cur;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H, w = W, n = H * W;
r = R, c = C;
if (n > 10000) cout << "parumna" << endl;
row_min = new SGT(n, INF, [](int a, int b) { return min(a, b); });
row_max = new SGT(n, -1, [](int a, int b) { return max(a, b); });
col_min = new SGT(n, INF, [](int a, int b) { return min(a, b); });
col_max = new SGT(n, -1, [](int a, int b) { return max(a, b); });
for (int i = 0; i < n; i++) {
updateAllSGT(i, r[i], c[i]);
}
}
int swap_seats(int a, int b) {
updateAllSGT(a, r[b], c[b]);
updateAllSGT(b, r[a], c[a]);
swap(r[a], r[b]);
swap(c[a], c[b]);
int ans = 0, i = 0;
while (i < n) {
int a = area(i);
ans += (a == i + 1);
i = (a == i + 1 ? i + 1 : a - 1);
}
return ans;
}
