#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
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;
}
};
int h, w;
vector<int> r, c;
segtree *str, *stc;
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);
}
inline int calc(int r1, int c1, int r2, int c2) {
int he = r2 - r1 + 1, we = c2 - c1 + 1;
int amt = he * we;
return amt;
}
int swap_seats(int a, int b) {
// perform swap
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]);
// count
int res = 0;
int r1, c1, r2, c2;
r1 = r2 = r[0];
c1 = c2 = c[0];
res += calc(r1, c1, r2, c2) == 1;
int i = 1;
while (i < h * w) {
auto [mnr, mxr] = str->query(0, i);
r1 = min(r1, mnr);
r2 = max(r2, mxr);
auto [mnc, mxc] = stc->query(0, i);
c1 = min(c1, mnc);
c2 = max(c2, mxc);
int que = calc(r1, c1, r2, c2);
// cerr << i sp r1 sp c1 sp r2 sp c2 sp que << endl;
if (que == i+1) res++;
// cerr << i sp res << endl;
if (i == max(i+1, que-1)) assert(0);
i = max(i+1, que-1);
}
return res;
}
