#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 20;
struct node {
int maxR, minR, maxC, minC;
node(): maxR(0), minR(0), maxC(0), minC(0) {};
node(int _maxR, int _minR, int _maxC, int _minC): maxR(_maxR), minR(_minR), maxC(_maxC), minC(_minC) {};
};
node merge(node left, node right) {
return node(max(left.maxR, right.maxR), min(left.minR, right.minR), max(left.maxC, right.maxC), min(left.minC, right.minC));
}
node tree[maxN * 4];
int maxR[maxN];
int minR[maxN];
int maxC[maxN];
int minC[maxN];
int R[maxN];
int C[maxN];
priority_queue<int, vector<int>, greater<int>> posR[maxN];
priority_queue<int, vector<int>, greater<int>> posC[maxN];
int N, H, W;
int cnt;
bool sub3;
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = node(R[lt], R[lt], C[lt], C[lt]);
return;
}
int mt = (lt + rt) >> 1;
build(id << 1, lt, mt);
build(id << 1 | 1, mt + 1, rt);
tree[id] = merge(tree[id << 1], tree[id << 1 | 1]);
}
void update(int id, int lt, int rt, int pos) {
if (lt == rt) {
tree[id] = node(R[lt], R[lt], C[lt], C[lt]);
return;
}
int mt = (lt + rt) >> 1;
if (pos <= mt) {
update(id << 1, lt, mt, pos);
}
else {
update(id << 1 | 1, mt + 1, rt, pos);
}
tree[id] = merge(tree[id << 1], tree[id << 1 | 1]);
}
node get(int id, int lt, int rt, int pos) {
if (lt == rt) {
return tree[id];
}
int mt = (lt + rt) >> 1;
if (pos <= mt) {
return get(id << 1, lt, mt, pos);
}
else {
return merge(tree[id << 1], get(id << 1 | 1, mt + 1, rt, pos));
}
};
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++) {
posR[R[i]].push(i);
posC[C[i]].push(i);
}
build(1, 1, N);
}
else {
minR[0] = H + 1;
minC[0] = W + 1;
for (int i = 1; i <= N; i++) {
maxR[i] = max(R[i], maxR[i - 1]);
minR[i] = min(R[i], minR[i - 1]);
maxC[i] = max(C[i], maxC[i - 1]);
minC[i] = min(C[i], minC[i - 1]);
if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
cnt++;
}
}
}
}
int swap_seats(int a, int b) {
if (sub3) {
a++;
b++;
swap(R[a], R[b]);
swap(C[a], C[b]);
update(1, 1, N, a);
update(1, 1, N, b);
posR[R[a]].push(a);
posC[C[a]].push(a);
posR[R[b]].push(b);
posC[C[b]].push(b);
priority_queue<int> cands;
for (int i = 1; i <= H; i++) {
int pos = -1;
while (pos == -1 && !posR[i].empty()) {
if (R[posR[i].top()] == i) {
pos = posR[i].top();
break;
}
else {
posR[i].pop();
}
}
if (pos > 1) {
cands.push(pos - 1);
}
}
for (int i = 1; i <= W; i++) {
int pos = -1;
while (pos == -1 && !posC[i].empty()) {
if (C[posC[i].top()] == i) {
pos = posC[i].top();
break;
}
else {
posC[i].pop();
}
}
if (pos > 1) {
cands.push(pos - 1);
}
}
int pos = -1;
cnt = 1;
while (!cands.empty()) {
if (cands.top() != pos) {
pos = cands.top();
node bounds = get(1, 1, N, pos);
if ((bounds.maxR - bounds.minR + 1) * (bounds.maxC - bounds.minC + 1) == pos) {
cnt++;
}
}
cands.pop();
}
return cnt;
}
else {
a++;
b++;
if (a > b) {
swap(a, b);
}
for (int i = a; i <= b; i++) {
if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
cnt--;
}
}
swap(R[a], R[b]);
swap(C[a], C[b]);
for (int i = a; i <= b; i++) {
maxR[i] = max(R[i], maxR[i - 1]);
minR[i] = min(R[i], minR[i - 1]);
maxC[i] = max(C[i], maxC[i - 1]);
minC[i] = min(C[i], minC[i - 1]);
if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
cnt++;
}
}
return cnt;
}
}
