#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;
}
}
int get(int l, int r) { //mx - mn + 1
l += sz;
r += sz;
assert(l < r);
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 Max - Min + 1;
}
};
vector<int> x, y;
vector<bool> ans;
int n, m, s, sum = 0;
SegTree R, C;
bool is_good(int k) {
return R.get(0, k + 1) * C.get(0, k + 1) == (k + 1);
}
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);
for (int i = 0; i < s; ++i) {
ans[i] = is_good(i);
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]);
for (int i = a; i <= b; ++i) {
sum -= ans[i];
ans[i] = is_good(i);
sum += ans[i];
}
return sum;
}
