#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 20;
int max_R[maxN];
int min_R[maxN];
int max_C[maxN];
int min_C[maxN];
int R[maxN];
int C[maxN];
priority_queue<int, vector<int>, greater<int>> pos_R[maxN];
priority_queue<int, vector<int>, greater<int>> pos_C[maxN];
int N, H, W;
int cnt;
bool sub3;
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
H = _H;
W = _W;
N = H * W;
sub3 = (H <= 1000 && W <= 1000);
for (int i = 1; i <= N; i++) {
R[i] = _R[i - 1] + 1;
C[i] = _C[i - 1] + 1;
}
if (sub3) {
for (int i = 1; i <= N; i++) {
pos_R[R[i]].push(i);
pos_C[C[i]].push(i);
}
}
else {
min_R[0] = H + 1;
min_C[0] = W + 1;
for (int i = 1; i <= N; i++) {
max_R[i] = max(R[i], max_R[i - 1]);
min_R[i] = min(R[i], min_R[i - 1]);
max_C[i] = max(C[i], max_C[i - 1]);
min_C[i] = min(C[i], min_C[i - 1]);
if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
cnt++;
}
}
}
}
int swap_seats(int a, int b) {
a++;
b++;
if (sub3) {
swap(R[a], R[b]);
swap(C[a], C[b]);
min_R[0] = H + 1;
min_C[0] = W + 1;
for (int i = 1; i <= N; i++) {
max_R[i] = max(R[i], max_R[i - 1]);
min_R[i] = min(R[i], min_R[i - 1]);
max_C[i] = max(C[i], max_C[i - 1]);
min_C[i] = min(C[i], min_C[i - 1]);
}
pos_R[R[a]].push(a);
pos_C[C[a]].push(a);
pos_R[R[b]].push(b);
pos_C[C[b]].push(b);
cnt = 1;
for (int i = 1; i <= H; i++) {
int pos = -1;
while (pos == -1 && !pos_R[i].empty()) {
if (R[pos_R[i].top()] == i) {
pos = pos_R[i].top();
break;
}
else {
pos_R[i].pop();
}
}
if (pos > 1 && (max_R[pos - 1] - min_R[pos - 1] + 1) * (max_C[pos - 1] - min_C[pos - 1] + 1) == pos - 1) {
cnt++;
}
}
for (int i = 1; i <= W; i++) {
int pos = -1;
while (pos == -1 && !pos_C[i].empty()) {
if (C[pos_C[i].top()] == i) {
pos = pos_C[i].top();
break;
}
else {
pos_C[i].pop();
}
}
if (pos > 1 && (max_R[pos - 1] - min_R[pos - 1] + 1) * (max_C[pos - 1] - min_C[pos - 1] + 1) == pos - 1) {
cnt++;
}
}
return cnt;
}
else {
if (a > b) {
swap(a, b);
}
for (int i = a; i <= b; i++) {
if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
cnt--;
}
}
for (int i = a; i <= b; i++) {
max_R[i] = max(R[i], max_R[i - 1]);
min_R[i] = min(R[i], min_R[i - 1]);
max_C[i] = max(C[i], max_C[i - 1]);
min_C[i] = min(C[i], min_C[i - 1]);
if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
cnt++;
}
}
return cnt;
}
}
