#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef array<int, 4> ar4;
const int MAXN = 1e6+5;
int h, w, n;
pii points[MAXN];
int vals[4][2*MAXN];
int ans = 0;
void single(int i) {
vals[0][i] = min(vals[0][2*i], vals[0][2*i+1]);
vals[1][i] = max(vals[1][2*i], vals[1][2*i+1]);
vals[2][i] = min(vals[2][2*i], vals[2][2*i+1]);
vals[3][i] = max(vals[3][2*i], vals[3][2*i+1]);
}
void set_val(int i) {
vals[0][i+n] = points[i].first;
vals[1][i+n] = points[i].first;
vals[2][i+n] = points[i].second;
vals[3][i+n] = points[i].second;
}
void upd(int p) {
set_val(p);
for (p = (p+n)/2; p > 0; p /= 2) single(p);
}
void combine(ar4 &a, int i) {
a[0] = min(a[0], vals[0][i]);
a[1] = max(a[1], vals[1][i]);
a[2] = min(a[2], vals[2][i]);
a[3] = max(a[3], vals[3][i]);
}
int get(int i) {
ar4 res({h, 0, w, 0});
for (int l = n, r = i+1+n; r > l; r /= 2, l /= 2) {
if (l & 1) combine(res, l++);
if (r & 1) combine(res, --r);
}
return (res[1]-res[0]+1)*(res[3]-res[2]+1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H;
w = W;
n = h*w;
assert(n > 1e4);
ar4 cur({h, 0, w, 0});
for (int i = 0; i < n; i++) {
points[i] = pii(R[i], C[i]);
set_val(i);
combine(cur, i+n);
ans += ((cur[1]-cur[0]+1)*(cur[3]-cur[2]+1) == i+1);
}
for (int i = n-1; i > 0; i--) single(i);
}
int swap_seats(int a, int b) {
for (int i = min(a, b); i <= max(a, b); i++) ans -= (get(i) == i+1);
swap(points[a], points[b]);
upd(a);
upd(b);
for (int i = min(a, b); i <= max(a, b); i++) {
if (get(i) == i+1) {
ans++;
// cerr << i << '\n';
}
// ans += (get(i) == i+1);
}
// cerr << '\n';
return ans;
}
