#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
vector<int> mx, mn;
int sz = 1;
SegTree() = default;
SegTree(int n, vector<int> a) {
sz = n;
mn.resize(sz << 1), mx.resize(sz << 1);
for (int i = 0; i < n; ++i) {
mn[i + sz] = mx[i + sz] = a[i];
}
for (int i = sz - 1; i > 0; --i) {
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
}
}
void modify(int i, int val) {
i += sz;
mn[i] = mx[i] = val;
i >>= 1;
while (i > 0) {
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
i >>= 1;
}
}
pair<int, int> get(int l, int r) {
l += sz;
r += sz;
int Max = INT_MIN, Min = INT_MAX;
while (l < r) {
if (l & 1) {
Max = max(Max, mx[l]);
Min = min(Min, mn[l]);
++l;
}
if (r & 1) {
--r;
Max = max(Max, mx[r]);
Min = min(Min, mn[r]);
}
l >>= 1;
r >>= 1;
}
return {Min, Max};
}
};
vector<int> x, y;
vector<bool> ans;
int n, m, s, sum = 0;
SegTree R, C;
void upd(int& mx, int & mn, int val) {
mx = max(mx, val);
mn = min(mn, val);
}
void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C) {
swap(x, _R), swap(y, _C);
n = H, m = W;
s = n * m;
R = SegTree(s, x);
C = SegTree(s, y);
ans.resize(s);
int mxR = INT_MIN, mnR = INT_MAX;
int mxC = mxR, mnC = mnR;
for (int i = 0; i < s; ++i) {
upd(mxR, mnR, x[i]);
upd(mxC, mnC, y[i]);
ans[i] = (mxR - mnR + 1) * (mxC - mnC + 1) == (i + 1);
sum += ans[i];
}
}
int swap_seats(int a, int b) {
if (a > b) {
swap(a, b);
}
swap(x[a], x[b]);
swap(y[a], y[b]);
R.modify(a, x[a]), R.modify(b, x[b]);
C.modify(a, y[a]), C.modify(b, y[b]);
auto [mnC, mxC] = C.get(0, a);
auto [mnR, mxR] = R.get(0, a);
for (int i = a; i <= b; ++i) {
sum -= ans[i];
upd(mxR, mnR, x[i]);
upd(mxC, mnC, y[i]);
ans[i] = (mxR - mnR + 1) * (mxC - mnC + 1) == (i + 1);
sum += ans[i];
}
return sum;
}
