#include "seats.h"
#include <algorithm>
#include <vector>
using namespace std;
constexpr int inf = 1e9;
struct Tree {
struct T {
int mn = inf, mx = -inf;
static T from(int x) { return {x, x}; }
T static combine(T f, T s) { return {min(f.mn, s.mn), max(f.mx, s.mx)}; }
};
vector<T> tree;
void pull(int i) { tree[i] = T::combine(tree[2 * i], tree[2 * i + 1]); }
void init(vector<int> const &base) {
int n = base.size();
tree.resize(4 * n);
_build(1, 0, n - 1, base);
}
void _build(int i, int l, int r, vector<int> const &base) {
if (l == r) {
tree[i] = T::from(base[l]);
return;
}
int m = (l + r) / 2;
_build(2 * i, l, m, base);
_build(2 * i + 1, m + 1, r, base);
pull(i);
}
T get(int i, int l, int r, int lb, int rb) const {
if (r < lb || l > rb) {
return {};
}
if (lb <= l && r <= rb) {
return tree[i];
}
int m = (l + r) / 2;
return T::combine(get(2 * i, l, m, lb, rb), get(2 * i + 1, m + 1, r, lb, rb));
}
void update(int i, int l, int r, int pos, int x) {
if (pos < l || pos > r) {
return;
}
if (l == r) {
tree[i] = T::from(x);
return;
}
int m = (l + r) / 2;
update(2 * i, l, m, pos, x);
update(2 * i + 1, m + 1, r, pos, x);
pull(i);
}
};
vector<pair<int, int>> pos;
vector<pair<pair<int, int>, pair<int, int>>> bounds;
Tree rt, ct;
int n, res;
int get_square(pair<pair<int, int>, pair<int, int>> a) {
auto [r, c] = a;
return (r.second - r.first + 1) * (c.second - c.first + 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H * W;
pos.resize(n);
bounds.resize(n);
res = 0;
pair<int, int> rr{1e9, -1}, cc{1e9, -1};
for (int i = 0; i < n; i++) {
pos[i] = {R[i], C[i]};
rr.first = min(rr.first, pos[i].first);
rr.second = max(rr.second, pos[i].first);
cc.first = min(cc.first, pos[i].second);
cc.second = max(cc.second, pos[i].second);
bounds[i] = {rr, cc};
res += get_square(bounds[i]) == i + 1;
}
// rt.init(R);
// ct.init(C);
}
int swap_seats(int a, int b) {
if (a > b) {
swap(a, b);
}
swap(pos[a], pos[b]);
pair<int, int> rr{1e9, -1}, cc{1e9, -1};
if (a) {
rr = bounds[a - 1].first;
cc = bounds[a - 1].second;
}
for (int i = a; i < b; i++) {
res -= get_square(bounds[i]) == i + 1;
rr.first = min(rr.first, pos[i].first);
rr.second = max(rr.second, pos[i].first);
cc.first = min(cc.first, pos[i].second);
cc.second = max(cc.second, pos[i].second);
bounds[i] = {rr, cc};
res += get_square(bounds[i]) == i + 1;
}
return res;
// rt.update(1, 0, n - 1, a, r[a]);
// rt.update(1, 0, n - 1, b, r[b]);
//
// ct.update(1, 0, n - 1, a, c[a]);
// ct.update(1, 0, n - 1, b, c[b]);
//
//
// int res = 0;
// int i = 0;
// while (i < n) {
// auto rr = rt.get(1, 0, n - 1, 0, i);
// auto cc = ct.get(1, 0, n - 1, 0, i);
// int sz = (rr.mx - rr.mn + 1) * (cc.mx - cc.mn + 1);
// if (sz == i + 1) {
// res++;
// ++i;
// } else {
// i = sz - 1;
// }
// }
// return res;
}
