#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
int n, h, w, r[1000000], c[1000000], rmin[2000000], rmax[2000000], cmin[2000000], cmax[2000000];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
n = R.size();
rep(i, n) {
r[i] = rmin[n + i] = rmax[n + i] = R[i];
c[i] = cmin[n + i] = cmax[n + i] = C[i];
}
for (int i = n - 1; i > 0; i--) {
rmin[i] = min(rmin[i * 2], rmin[i * 2 + 1]);
rmax[i] = max(rmax[i * 2], rmax[i * 2 + 1]);
cmin[i] = min(cmin[i * 2], cmin[i * 2 + 1]);
cmax[i] = max(cmax[i * 2], cmax[i * 2 + 1]);
}
}
int swap_seats(int a, int b) {
rmin[n + a] = rmax[n + a] = r[b];
cmin[n + a] = cmax[n + a] = c[b];
rmin[n + b] = rmax[n + b] = r[a];
cmin[n + b] = cmax[n + b] = c[a];
swap(r[a], r[b]);
swap(c[a], c[b]);
int i = n + a;
while (i > 1) {
i /= 2;
rmin[i] = min(rmin[i * 2], rmin[i * 2 + 1]);
rmax[i] = max(rmax[i * 2], rmax[i * 2 + 1]);
cmin[i] = min(cmin[i * 2], cmin[i * 2 + 1]);
cmax[i] = max(cmax[i * 2], cmax[i * 2 + 1]);
}
i = n + b;
while (i > 1) {
i /= 2;
rmin[i] = min(rmin[i * 2], rmin[i * 2 + 1]);
rmax[i] = max(rmax[i * 2], rmax[i * 2 + 1]);
cmin[i] = min(cmin[i * 2], cmin[i * 2 + 1]);
cmax[i] = max(cmax[i * 2], cmax[i * 2 + 1]);
}
int res = 2;
i = 2;
while(i < n) {
int ra = n, rb = -1, ca = n, cb = -1, lo = n, hi = n + i;
while (lo < hi) {
if (lo % 2) {
ra = min(ra, rmin[lo]);
rb = max(rb, rmax[lo]);
ca = min(ca, cmin[lo]);
cb = max(cb, cmax[lo++]);
}
if (hi % 2) {
ra = min(ra, rmin[--hi]);
rb = max(rb, rmax[hi]);
ca = min(ca, cmin[hi]);
cb = max(cb, cmax[hi]);
}
lo /= 2;
hi /= 2;
}
if ((rb - ra + 1) * (cb - ca + 1) == i) {
res++;
i++;
} else {
i = (rb - ra + 1) * (cb - ca + 1);
}
}
return res;
}
