#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int n, m, R[MAXN], C[MAXN], k;
vector<vector<int>> A;
vector<int> sg[MAXN];
inline void update(int t, int ind, int val, int l, int r, int v) {
if (l == r) sg[t][v] = val;
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(t, ind, val, l, mid, v << 1);
else update(t, ind, val, mid + 1, r, v << 1 | 1);
sg[t][v] = max(sg[t][v << 1], sg[t][v << 1 | 1]);
}
}
inline int query(int t, int ql, int qr, int l, int r, int v) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sg[t][v];
int mid = (l + r) >> 1;
return max(query(t, ql, qr, l, mid, v << 1),
query(t, ql, qr, mid + 1, r, v << 1 | 1));
}
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
n = H_, m = W_;
k = n * m;
for (int i = 0; i < n; i++)
sg[i].resize(4 * m);
for (int i = 0; i < m; i++)
sg[n + i].resize(4 * n);
A.resize(n + 3);
for (int i = 0; i < n; i++) {
A[i].resize(m + 3);
}
for (int i = 0; i < n * m; i++) {
R[i] = R_[i];
C[i] = C_[i];
A[R[i]][C[i]] = i;
update(R[i], C[i], i, 0, m - 1, 1);
update(n + C[i], R[i], i, 0, n - 1, 1);
}
}
int swap_seats(int a, int b) {
swap(A[R[a]][C[a]], A[R[b]][C[b]]);
swap(R[a], R[b]);
swap(C[a], C[b]);
update(R[a], C[a], a, 0, m - 1, 1);
update(n + C[a], R[a], a, 0, n - 1, 1);
update(R[b], C[b], b, 0, m - 1, 1);
update(n + C[b], R[b], b, 0, n - 1, 1);
int rl = R[0], rr = R[0], cl = C[0], cr = C[0], mx = 0;
int ans = 1;
while (rl > 0 || rr < n - 1 || cl > 0 || cr < m - 1) {
int best_type = -1, best = numeric_limits<int>::max();
if (rl > 0) {
int poss = A[rl - 1][cl];
if (poss < best) {
best_type = 0;
best = poss;
}
}
if (cl > 0) {
int poss = A[rl][cl - 1];
if (poss < best) {
best_type = 1;
best = poss;
}
}
if (rr < n - 1) {
int poss = A[rr + 1][cl];
if (poss < best) {
best_type = 2;
best = poss;
}
}
if (cr < m - 1) {
int poss = A[rl][cr + 1];
if (poss < best) {
best_type = 3;
best = poss;
}
}
if (best_type == 0) {
rl--;
mx = max(mx, query(rl, cl, cr, 0, m - 1, 1));
} else if (best_type == 2) {
rr++;
mx = max(mx, query(rr, cl, cr, 0, m - 1, 1));
} else if (best_type == 1) {
cl--;
mx = max(mx, query(n + cl, rl, rr, 0, n - 1, 1));
} else {
cr++;
mx = max(mx, query(n + cr, rl, rr, 0, n - 1, 1));
}
if (mx + 1 == (rr - rl + 1) * (cr - cl + 1))
ans++;
}
return ans;
}
