#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define x first
#define y second
const int mxn = 1e6 + 10;
int n, m;
struct node {
int xMin, xMax, yMin, yMax;
node(int x1, int y1, int x2, int y2) : xMin(x1), yMin(y1), xMax(x2), yMax(y2) {}
node(int x, int y) : xMin(x), yMin(y), xMax(x), yMax(y) {}
node() : xMin(1e9), yMin(1e9), xMax(-1e9), yMax(-1e9) {}
node operator+(node a) {
return node(min(a.xMin, xMin), min(a.yMin, yMin), max(a.xMax, xMax), max(a.yMax, yMax));
}
bool operator==(node a) {
return a.xMax == xMax && a.xMin == xMin && a.yMax == yMax && a.yMin == yMin;
}
};
vector<node> arr;
node d[mxn * 4];
void update(int l, int r, int i, int x, node val) {
if(l == r) {
d[i] = val;
return;
}
int m = (l + r) / 2;
if(x <= m) update(l, m, i * 2, x, val);
else update(m + 1, r, i * 2 + 1, x, val);
d[i] = d[i * 2] + d[i * 2 + 1];
}
node get(int l, int r, int i, int x) {
if(r <= x) return d[i];
int m = (l + r) / 2;
if(x <= m) return get(l, m, i * 2, x);
return d[i * 2] + get(m + 1, r, i * 2 + 1, x);
}
int query(int l, int r, int i, node val) {
if(l == r) return l + (get(0, n * m - 1, 1, l) == val);
int m = (l + r) / 2;
if(val.xMin > d[i * 2].xMin || val.xMax < d[i * 2].xMax || val.yMin > d[i * 2].yMin || val.yMax < d[i * 2].yMax)
return query(l, m, i * 2, val);
return query(m + 1, r, i * 2 + 1, val);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H;
m = W;
for(int i = 0; i < n * m; i++) {
arr.eb(R[i], C[i]);
update(0, n * m - 1, 1, i, arr[i]);
}
}
int swap_seats(int a, int b) {
update(0, n * m - 1, 1, a, arr[b]);
update(0, n * m - 1, 1, b, arr[a]);
swap(arr[a], arr[b]);
node now(1e9, 1e9, -1e9, -1e9);
int l = -1, ans = 0;
while(l < n * m) {
l = query(0, n * m - 1, 1, now);
if(now.xMax != -1e9 && (now.xMax - now.xMin + 1) * (now.yMax - now.yMin + 1) == l) ans++;
if(l < n * m) now = get(0, n * m - 1, 1, l);
}
return ans;
}
