#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int H, W;
std::vector<int> R, C;
struct segtree
{
int size;
vpii arr;
const pii NEUTRAL = {1 << 30, -(1 << 30)};
void init(vi &A)
{
size = 1;
while (size < sz(A))
size *= 2;
arr.assign(2 * size, NEUTRAL);
for (int i = 0; i < sz(A); ++i)
arr[i + size] = {A[i], A[i]};
for (int i = size - 1; i > 0; --i)
arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
}
pii combine(const pii &a, const pii &b)
{
return {min(a.first, b.first), max(a.second, b.second)};
}
void set(int i, int v)
{
i += size;
arr[i] = {v, v};
i /= 2;
while (i > 0)
{
arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
i /= 2;
}
}
pii query(int l, int r) { return query(l, r, 1, 0, size); }
pii query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return NEUTRAL;
int m = (lx + rx) / 2;
pii left = query(l, r, 2 * x, lx, m);
pii right = query(l, r, 2 * x + 1, m, rx);
return combine(left, right);
}
};
segtree segR;
segtree segC;
struct fenwick
{
vi arr;
void init(int size)
{
arr.assign(size + 1, 0);
}
void add(int i, int v)
{
++i;
while (i < sz(arr))
arr[i] += v, i += i & (~i + 1);
}
int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
int query(int i)
{
++i;
int ans = 0;
while (i > 0)
ans += arr[i], i -= i & (~i + 1);
return ans;
}
};
fenwick fen;
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C)
{
H = _H, W = _W;
R = _R, C = _C;
segR.init(R), segC.init(C);
fen.init(H * W);
int rmax = R[0], rmin = R[0];
int cmax = C[0], cmin = C[0];
int k = 0;
while (k < H * W)
{
tie(rmin, rmax) = segR.query(0, k + 1);
tie(cmin, cmax) = segC.query(0, k + 1);
int area = (rmax - rmin + 1) * (cmax - cmin + 1);
if (area == k + 1)
fen.add(k, 1), ++k;
else
{
assert(area - 1 > k);
k = area - 1;
}
}
}
int swap_seats(int a, int b)
{
if (a > b)
swap(a, b);
swap(R[a], R[b]), swap(C[a], C[b]);
segR.set(a, R[a]);
segC.set(a, C[a]);
segR.set(b, R[b]);
segC.set(b, C[b]);
int rmin, rmax, cmin, cmax;
tie(rmin, rmax) = segR.query(0, a + 1);
tie(cmin, cmax) = segC.query(0, a + 1);
for (int k = a; k < b + 1; ++k)
{
if (fen.query(k, k + 1))
fen.add(k, -1);
rmax = max(rmax, R[k]);
rmin = min(rmin, R[k]);
cmax = max(cmax, C[k]);
cmin = min(cmin, C[k]);
int area = (rmax - rmin + 1) * (cmax - cmin + 1);
if (area == k + 1)
fen.add(k, 1);
}
return fen.query(0, H * W);
}
