#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
const int INF = 1e9;
struct segtree {
int n, t;
vector<pair<int, int>> tree;
segtree(int l, int r, vector<int> &a) {
n = r+1;
t = 1;
while (t < n) t <<= 1;
tree.assign(2*t, {INF, -INF});
for (int i = 0; i < n; i++) {
tree[t + i] = {a[i], a[i]};
}
for (int i = t-1; i >= 0; i--) {
tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
}
}
void update(int ind, int upd) {
int i = t + ind;
tree[i] = {upd, upd};
for (i >>= 1; i; i >>= 1) {
tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
}
}
pair<int, int> query(int l, int r) {
l += t, r += t;
pair<int, int> res = {INF, -INF};
while (l <= r) {
if (l & 1) {
res.first = min(res.first, tree[l].first);
res.second = max(res.second, tree[l].second);
l++;
}
if (!(r & 1)) {
res.first = min(res.first, tree[r].first);
res.second = max(res.second, tree[r].second);
r--;
}
l >>= 1, r >>= 1;
}
return res;
}
};
struct sumtree {
int n, t;
vector<int> tree;
sumtree(int l, int r) {
n = r+1;
t = 1;
while (t < n) t <<= 1;
tree.assign(2*t, 0);
for (int i = 0; i < n; i++) {
tree[t + i] = 0;
}
for (int i = t-1; i >= 0; i--) {
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}
void update(int ind, int upd) {
int i = t + ind;
tree[i] = upd;
for (i >>= 1; i; i >>= 1) {
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}
int query(int l, int r) {
l += t, r += t;
int res = 0;
while (l <= r) {
if (l & 1) {
res += tree[l];
l++;
}
if (!(r & 1)) {
res += tree[r];
r--;
}
l >>= 1, r >>= 1;
}
return res;
}
};
int h, w;
vector<int> r, c;
sumtree *ts;
segtree *str, *stc;
bool check(int r1, int c1, int r2, int c2, int x) {
int he = r2 - r1 + 1, we = c2 - c1 + 1;
int amt = he * we;
return amt == x+1;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H, w = W, r = R, c = C;
str = new segtree(0, h*w-1, r);
stc = new segtree(0, h*w-1, c);
ts = new sumtree(0, h*w-1);
int r1 = INF, c1 = INF, r2 = -INF, c2 = -INF;
for (int i = 0; i < h * w; i++) {
r1 = min(r1, r[i]);
r2 = max(r2, r[i]);
c1 = min(c1, c[i]);
c2 = max(c2, c[i]);
ts->update(i, check(r1, c1, r2, c2, i));
}
}
int swap_seats(int a, int b) {
// perform swap
if (a > b) swap(a, b);
swap(r[a], r[b]);
swap(c[a], c[b]);
str->update(a, r[a]);
str->update(b, r[b]);
stc->update(a, c[a]);
stc->update(b, c[b]);
// update
a = max(0, a-5);
b = min(h*w-1, b+5);
auto [r1, r2] = str->query(0, a-1);
auto [c1, c2] = stc->query(0, a-1);
for (int i = a; i <= b; i++) {
r1 = min(r1, r[i]);
r2 = max(r2, r[i]);
c1 = min(c1, c[i]);
c2 = max(c2, c[i]);
ts->update(i, check(r1, c1, r2, c2, i));
}
return ts->query(0, h*w-1);
}
