#include <bits/stdc++.h>
#include "seats.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)
const int N = 1'000'005, inf = 1e9;
struct node {
int mn;
int lazy;
int cnt;
node() {
mn = 0;
lazy = 0;
cnt = 0;
}
node(int v) {
mn = v;
lazy = 0;
cnt = 1;
}
friend node operator+(const node &l, const node &r) {
node ret = l;
if (r.mn < ret.mn) {
ret = r;
} else if (r.mn == l.mn) {
ret.cnt += r.cnt;
}
return ret;
}
} seg[1 << 21];
void build(int i, int l, int r, vector<int> &v) {
if (l == r) {
seg[i] = v[l];
return;
}
build(i << 1, l, md, v);
build(i << 1 | 1, md + 1, r, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void process(int i, int l, int r) {
if (l != r) {
for (auto c : {i << 1, i << 1 | 1}) {
seg[c].lazy += seg[i].lazy;
}
}
seg[i].mn += seg[i].lazy;
seg[i].lazy = 0;
}
void upd(int i, int l, int r, int s, int e, int v) {
process(i, l, r);
if (s <= l && r <= e) {
seg[i].lazy += v;
process(i, l, r);
return;
}
if (r < s || e < l) {
return;
}
upd(i << 1, l, md, s, e, v);
upd(i << 1 | 1, md + 1, r, s, e, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
int n, m;
vector<int> r, c;
vector<vector<int>> t;
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n = _n, m = _m;
r = _r, c = _c;
t.resize(n);
for (int i = 0; i < n; i++) {
t[i].resize(m);
}
for (int i = 0; i < n * m; i++) {
t[r[i]][c[i]] = i;
}
int comps = 0;
vector<int> v(n * m);
for (int i = 0; i < n * m; i++) {
int p = c[i];
if (p - 1 >= 0 && p + 1 < m) {
comps -= t[0][p - 1] < i && t[0][p + 1] < i;
}
comps += (p == 0 || t[0][p - 1] > i) && (p + 1 == m || t[0][p + 1] > i);
v[i] = comps;
}
build(1, 0, n * m - 1, v);
}
void process(vector<int> pos, int coeff) {
sort(pos.begin(), pos.end());
pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
for (auto p : pos) {
if (p == -1 || p == m) continue;
int v = 0;
if (p - 1 >= 0 && p + 1 < m) {
v -= t[0][p - 1] < t[0][p] && t[0][p + 1] < t[0][p];
}
v += (p == 0 || t[0][p - 1] > t[0][p]) && (p + 1 == m || t[0][p + 1] > t[0][p]);
v *= coeff;
upd(1, 0, n * m - 1, t[0][p], n * m - 1, v);
}
}
int swap_seats(int x, int y) {
if (x > y) swap(x, y);
vector<int> v = {c[x] - 1, c[x], c[x] + 1, c[y] - 1, c[y], c[y] + 1};
process(v, -1);
swap(r[x], r[y]);
swap(c[x], c[y]);
t[r[x]][c[x]] = x;
t[r[y]][c[y]] = y;
process(v, 1);
node val = seg[1];
return val.cnt;
}
