#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
vector<int> r;
pair<int, int> V[MAX_N];
pair<int, int> mx[MAX_N], mi[MAX_N];
vector<int> lst;
struct inout_pq {
priority_queue<int> in, out;
void add(int x) { in.push(-x); }
void delect(int x) { out.push(-x); }
int return_top() {
while (in.size() && out.size() && in.top() == out.top()) {
in.pop();
out.pop();
}
if (in.size()) return -in.top();
return 0;
}
} X[MAX_N], Y[MAX_N];
int h, w, ans;
int sp(int a, int b) {
pair<int, int> x, y;
swap(V[a], V[b]);
if (a > b) swap(a, b);
a = a ? a : a + 1;
mx[0] = mi[0] = V[0];
for (int i = a; i <= b; i++) {
ans -= ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
mx[i].first = max(mx[i - 1].first, V[i].first);
mx[i].second = max(mx[i - 1].second, V[i].second);
mi[i].first = min(mi[i - 1].first, V[i].first);
mi[i].second = min(mi[i - 1].second, V[i].second);
ans += ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
}
return ans;
}
void sp_init() {
mx[0] = mi[0] = V[0];
swap(V[0], V[h * w - 1]);
ans = 1;
ans = sp(0, h * w - 1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
int i;
h = H;
w = W;
for (i = 0; i < H * W; i++) V[i] = {R[i], C[i]};
if (h + w >= 10000) {
sp_init();
return;
}
for (i = 0; i < H * W; i++) {
X[R[i]].add(i);
Y[C[i]].add(i);
}
}
int swap_seats(int a, int b) {
int i;
if (h + w >= 10000) return sp(a, b);
X[V[a].first].delect(a);
Y[V[a].second].delect(a);
X[V[b].first].delect(b);
Y[V[b].second].delect(b);
swap(V[a], V[b]);
X[V[a].first].add(a);
Y[V[a].second].add(a);
X[V[b].first].add(b);
Y[V[b].second].add(b);
lst.clear();
lst.resize(0);
for (i = 0; i < h; i++) lst.push_back(X[i].return_top());
for (i = 0; i < w; i++) lst.push_back(Y[i].return_top());
sort(lst.begin(), lst.end());
lst.erase(unique(lst.begin(), lst.end()), lst.end());
pair<int, int> x, y;
ans = 1;
x = {V[0].first, V[0].first};
y = {V[0].second, V[0].second};
for (int p : lst) {
ans += ((x.second - x.first + 1) * (y.second - y.first + 1) == p);
y.first = min(y.first, V[p].second);
y.second = max(y.second, V[p].second);
x.first = min(x.first, V[p].first);
x.second = max(x.second, V[p].first);
}
return ans;
}
