#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
v<v<int>> pos;
int n, m;
v<v<int>> mx;
v<int> c;
struct SegTree {
v<int> tree;
SegTree(int n) {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int u, int x) {
if (l > u || r < u) return;
if (l == r && r == u) {
tree[p] = x;
}
else {
int m = (l+r)/2;
query(2*p, l, m, u, x);
query(2*p+1, m+1, r, u, x);
tree[p] = tree[2*p] + tree[2*p+1];
}
}
};
SegTree* st;
void give_initial_chart(int H, int W, v<int> R, v<int> C) {
pos.resize(H*W);
c.assign(H*W, 0);
rep(i, 0, H*W) {
pos[i] = {R[i], C[i]};
}
int mxx, mnx, mxy, mny;
mxx = mnx = pos[0][0];
mxy = mny = pos[0][1];
mx.resize(H*W+1);
mx[1] = {mxx, mxy, mnx, mny};
c[0] = 1;
mx[0] = {-1, -1, 1000000000, 1000000000};
rep(i, 1, H*W) {
mxx = max(mxx, pos[i][0]);
mnx = min(mnx, pos[i][0]);
mxy = max(mxy, pos[i][1]);
mny = min(mny, pos[i][1]);
mx[i+1] = {mxx, mxy, mnx, mny};
int h = abs(mxx-mnx)+1;
int w = abs(mxy-mny)+1;
if (h*w == i+1) c[i] = 1;
else c[i] = 0;
}
st = new SegTree(H*W);
rep(i, 0, H*W) {
st->query(1, 0, H*W-1, i, c[i]);
}
n = H, m = W;
}
int swap_seats(int a, int b) {
int mnx, mny, mxx, mxy;
swap(pos[a][0], pos[b][0]);
swap(pos[a][1], pos[b][1]);
//a < b
if (a > b) swap(a, b);
mxx = mx[a][0], mxy = mx[a][1];
mnx = mx[a][2], mny = mx[a][3];
rep(i, a, b+1) {
mxx = max(mxx, pos[i][0]);
mnx = min(mnx, pos[i][0]);
mxy = max(mxy, pos[i][1]);
mny = min(mny, pos[i][1]);
mx[i+1] = {mxx, mxy, mnx, mny};
int h = abs(mxx-mnx)+1;
int w = abs(mxy-mny)+1;
if (h*w == i+1) c[i] = 1;
else c[i] = 0;
}
rep(i, a, b+1) {
st->query(1, 0, n*m-1, i, c[i]);
}
return st->tree[1];
}
