#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
struct rect {
int left, right, top, bot;
inline int size() {
return (right-left+1) * (bot-top+1);
}
inline int minSide() {
return min(right-left+1, bot-top+1);
}
static rect merge(const rect &a, const rect &b) {
return {min(a.left, b.left), max(a.right, b.right), min(a.top, b.top), max(a.bot, b.bot)};
}
};
int n, w, h, pow2;
vector<int> x, y;
vector<rect> seg;
rect segRect(ll low, ll high) {
low += pow2; high += pow2;
rect res = seg[low++];
while (low <= high) {
if (low & 1) res = rect::merge(res, seg[low++]);
if (!(high & 1)) res = rect::merge(res, seg[high--]);
low /= 2; high /= 2;
}
return res;
}
void give_initial_chart(int h1, int w1, vector<int> r, vector<int> c) {
w = w1; h = h1;
n = h*w;
x = c; y = r;
pow2 = 1ll << (ll)ceil(log2(n));
seg = vector<rect>(2*pow2);
for (int i = pow2; i < pow2+n; i++) {
seg[i] = {x[i-pow2], x[i-pow2], y[i-pow2], y[i-pow2]};
}
for (int i = pow2-1; i > 0; i--) {
seg[i] = rect::merge(seg[2*i], seg[2*i+1]);
}
}
int swap_seats(int a, int b) {
swap(x[a], x[b]);
swap(y[a], y[b]);
int res = 0;
rect r = {x[0], x[0], y[0], y[0]};
int i = 0;
while (i < n) {
if (r.size() == i+1) {
res++;
int nw = r.size() + r.minSide() - 1;
r = rect::merge(r, segRect(i+1, nw));
}
else {
int nw = r.size() - 1;
r = rect::merge(r, segRect(i+1, nw));
}
}
return res;
}
