#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int MAX_N = 1e6 + 5;
int H, W;
vector <int> R, C;
int tree[4 * MAX_N];
struct State {
int minR, maxR, minC, maxC;
}state[MAX_N];
void update(int idx, int l, int r, int q, int v) {
if(l == r) {
tree[idx] = v;
return;
}
int mid = (l + r) / 2;
if(q <= mid) {
update(idx * 2, l, mid, q, v);
}
else {
update(idx * 2 + 1, mid + 1, r, q, v);
}
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c) {
H = h, W = w, R = r, C = c;
int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
for(int i = 0; i < H * W; i++) {
minR = min(minR, R[i]);
maxR = max(maxR, R[i]);
minC = min(minC, C[i]);
maxC = max(maxC, C[i]);
state[i] = {minR, maxR, minC, maxC};
update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
}
}
int swap_seats(int a, int b) {
if(a > b) {
swap(a, b);
}
swap(R[a], R[b]), swap(C[a], C[b]);
int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
if(a > 0) {
minR = state[a - 1].minR;
maxR = state[a - 1].maxR;
minC = state[a - 1].minC;
maxC = state[a - 1].maxC;
}
for(int i = a; i <= b; i++) {
minR = min(minR, R[i]);
maxR = max(maxR, R[i]);
minC = min(minC, C[i]);
maxC = max(maxC, C[i]);
state[i] = {minR, maxR, minC, maxC};
update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
}
return tree[1];
}
