#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
template<typename T> bool ckmin(T& a, T b) {
return !(a <= b) && (a = b), true;
}
template<typename T> bool ckmax(T& a, T b) {
return !(a >= b) && (a = b), true;
}
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 = -inf, Min = inf;
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;
vector<set<int>> placeX, placeY;
SegTree R, C;
bool upd(int &mx, int &mn, int val) {
bool yay = false;
yay |= ckmax(mx, val);
yay |= ckmin(mn, val);
return yay;
}
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);
placeX.assign(n, {});
placeY.assign(m, {});
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]);
placeX[x[i]].insert(i);
placeY[y[i]].insert(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);
}
if (n > 1000 || m > 1000) {
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;
} else {
vector<array<int, 3>> updates;
//0 = row, 1 = column
placeX[x[a]].erase(a);
placeY[y[a]].erase(a);
placeX[x[b]].erase(b);
placeY[y[b]].erase(b);
swap(x[a], x[b]);
swap(y[a], y[b]);
placeX[x[a]].insert(a);
placeY[y[a]].insert(a);
placeX[x[b]].insert(b);
placeY[y[b]].insert(b);
for (int i = 0; i < n; ++i) {
updates.push_back({*placeX[i].begin(), 0, i});
}
for (int i = 0; i < m; ++i) {
updates.push_back({*placeY[i].begin(), 1, i});
}
sort(updates.begin(), updates.end());
vector<array<int, 3>> left;
int mn[2] = {inf, inf};
int mx[2] = {-inf, -inf};
for (auto [k, tp, v] : updates) {
if (upd(mx[tp], mn[tp], v)) {
left.push_back({k, tp, v});
}
}
sum = 0;
mn[0] = mn[1] = inf;
mx[0] = mx[1] = -inf;
for (int i = 0; i < (int)left.size(); ++i) {
auto [k, tp, v] = left[i];
upd(mx[tp], mn[tp], v);
if (mn[0] == inf || mn[1] == inf) {
continue;
}
int val = (mx[0] - mn[0] + 1) * (mx[1] - mn[1] + 1);
if (val < k + 1 || (i != (int)left.size() - 1 && left[i + 1][0] + 1 <= val)) {
continue;
}
sum += 1;
}
return sum;
}
}
