#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> r, c;
vector<vector<int>> mat;
vector<int> memo;
vector<int> mup, mdown, mleft, mright, mma;
int n, m, ans = 1;
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
r = _r; c = _c;
n = _n; m = _m;
mat.resize(n, vector<int>(m));
for (int i = 0; i < n * m; i++) {
mat[r[i]][c[i]] = i;
}
memo.resize(n * m);
memo[0] = 1;
int up = r[0], down = r[0];
int left = c[0], right = c[0];
int ma = 0;
for (int i = 1; i < n * m; i++) {
bool flag = 0;
while (up > r[i]) {
up--; flag = 1;
for (int j = left; j <= right; j++) ma = max(ma, mat[up][j]);
}
while (down < r[i]) {
down++; flag = 1;
for (int j = left; j <= right; j++) ma = max(ma, mat[down][j]);
}
while (left > c[i]) {
left--; flag = 1;
for (int j = up; j <= down; j++) ma = max(ma, mat[j][left]);
}
while (right < c[i]) {
right++; flag = 1;
for (int j = up; j <= down; j++) ma = max(ma, mat[j][right]);
}
int dim = (down - up + 1) * (right - left + 1);
if (flag && ma == dim - 1) {
ans++;
memo[i] = 1;
}
mup.push_back(up);
mdown.push_back(down);
mleft.push_back(left);
mright.push_back(right);
mma.push_back(ma);
}
}
int swap_seats(int a, int b) {
if (a > b) swap(a, b);
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
int up = r[0], down = r[0];
int left = c[0], right = c[0];
int ma = 0;
if (a) {
up = mup[a - 1];
down = mdown[a - 1];
left = mleft[a - 1];
right = mright[a - 1];
ma = mma[a - 1];
} else a++;
for (int i = a; i <= b; i++) {
bool flag = 0;
while (up > r[i]) {
up--; flag = 1;
for (int j = left; j <= right; j++) ma = max(ma, mat[up][j]);
}
while (down < r[i]) {
down++; flag = 1;
for (int j = left; j <= right; j++) ma = max(ma, mat[down][j]);
}
while (left > c[i]) {
left--; flag = 1;
for (int j = up; j <= down; j++) ma = max(ma, mat[j][left]);
}
while (right < c[i]) {
right++; flag = 1;
for (int j = up; j <= down; j++) ma = max(ma, mat[j][right]);
}
ans -= memo[i];
memo[i] = 0;
int dim = (down - up + 1) * (right - left + 1);
if (flag && ma == dim - 1) memo[i] = 1;
ans += memo[i];
mup[i] = up;
mdown[i] = down;
mleft[i] = left;
mright[i] = right;
mma[i] = ma;
}
return ans;
}
