#include "seats.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
const int MAXN = 1e6 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
int pos[MAXN], a[MAXN], n, h, w;
int v[MAXN];
bool flag = 0;
int ev (int i) {
int sum = 0;
sum += (a[pos[i] - 1] < i ? -1 : 1);
sum += (a[pos[i] + 1] < i ? -1 : 1);
return sum;
}
using info = array <int, 3>;
info make (int x) {
return {x, 1, x};
}
info merge (info a, info b) {
b[0] += a[2];
if (a[0] < b[0]) {
return {a[0], a[1], a[2] + b[2]};
} else if (a[0] > b[0]) {
return {b[0], b[1], a[2] + b[2]};
} else {
return {a[0], a[1] + b[1], a[2] + b[2]};
}
}
struct SegmentTree {
vector <info> tree;
void init (int n) {
tree.resize(4 * n);
}
void build (int l, int r, int node) {
if (l == r) {
tree[node] = make(v[l]);
} else {
build(l, mid, tl); build(mid + 1, r, tr);
tree[node] = merge(tree[tl], tree[tr]);
}
}
void update (int l, int r, int a, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = make(v[a]);
return;
}
update(l, mid, a, tl); update(mid + 1, r, a, tr);
tree[node] = merge(tree[tl], tree[tr]);
}
info get (int l, int r, int a, int node) {
if (l == r) {
return tree[node];
}
if (a <= mid) return get(l, mid, a, tl);
else return get(mid + 1, r, a, tr);
}
} cur;
struct SegmentTree2 {
int a[MAXN << 2];
pair <int, int> tree[MAXN << 2];
pair <int, int> merge (pair <int, int> x, pair <int, int> y) {
return {min(x.first, y.first), max(x.second, y.second)};
}
void init (int l, int r, int node) {
if (l == r) {
tree[node] = {a[l], a[l]};
} else {
init(l, mid, tl); init(mid + 1, r, tr);
tree[node] = merge(tree[tl], tree[tr]);
}
}
void update (int l, int r, int a, int b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = {b, b};
return;
}
update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
tree[node] = merge(tree[tl], tree[tr]);
}
pair <int, int> get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return {1e9, 0};
if (l >= a && r <= b) return tree[node];
return merge(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
}
} c1, c2;
vector <int> rr, cc;
void give_initial_chart (int H, int W, vector <int> R, vector <int> C) {
rr = R; cc = C;
h = H; w = W;
flag = 0;
if (h == 1) {
flag = 1;
n = w;
for (int i = 1; i <= n; i++) {
a[C[i - 1] + 1] = i;
pos[i] = C[i - 1] + 1;
}
a[0] = a[n + 1] = n + 1;
for (int i = 1; i <= n; i++) {
v[i] = ev(i);
}
cur.init(n); cur.build(1, n, 1);
return;
}
for (int i = 0; i < h * w; i++) {
c1.a[i] = R[i]; c2.a[i] = C[i];
}
c1.init(0, h * w - 1, 1); c2.init(0, h * w - 1, 1);
}
int swap_seats (int A, int B) {
if (flag) {
A++; B++;
v[A] = 0, cur.update(1, n, A, 1);
if (pos[A] != 1) v[a[pos[A] - 1]] = 0, cur.update(1, n, a[pos[A] - 1], 1);
if (pos[A] != n) v[a[pos[A] + 1]] = 0, cur.update(1, n, a[pos[A] + 1], 1);
v[B] = 0, cur.update(1, n, B, 1);
if (pos[B] != 1) v[a[pos[B] - 1]] = 0, cur.update(1, n, a[pos[B] - 1], 1);
if (pos[B] != n) v[a[pos[B] + 1]] = 0, cur.update(1, n, a[pos[B] + 1], 1);
swap(a[pos[A]], a[pos[B]]);
swap(pos[A], pos[B]);
v[A] = ev(A), cur.update(1, n, A, 1);
if (pos[A] != 1) v[a[pos[A] - 1]] = ev(a[pos[A] - 1]), cur.update(1, n, a[pos[A] - 1], 1);
if (pos[A] != n) v[a[pos[A] + 1]] = ev(a[pos[A] + 1]), cur.update(1, n, a[pos[A] + 1], 1);
v[B] = ev(B), cur.update(1, n, B, 1);
if (pos[B] != 1) v[a[pos[B] - 1]] = ev(a[pos[B] - 1]), cur.update(1, n, a[pos[B] - 1], 1);
if (pos[B] != n) v[a[pos[B] + 1]] = ev(a[pos[B] + 1]), cur.update(1, n, a[pos[B] + 1], 1);
return cur.tree[1][1];
}
swap(rr[A], rr[B]);
swap(cc[A], cc[B]);
if (h * w <= 10000) {
int ans = 0;
int r1 = 1e9, r2 = 0, c3 = 1e9, c4 = 0;
for (int i = 0; i < h * w; i++) {
r1 = min(r1, rr[i]);
r2 = max(r2, rr[i]);
c3 = min(c3, cc[i]);
c4 = max(c4, cc[i]);
if ((r2 - r1 + 1) * (c4 - c3 + 1) == i + 1) {
ans++;
}
}
return ans;
}
c1.update(0, h * w - 1, A, rr[A], 1);
c2.update(0, h * w - 1, A, cc[A], 1);
c1.update(0, h * w - 1, B, rr[B], 1);
c2.update(0, h * w - 1, B, cc[B], 1);
int pos = 0, ans = 0;
while (pos < h * w) {
auto [r1, r2] = c1.get(0, h * w - 1, 0, pos, 1);
auto [c3, c4] = c2.get(0, h * w - 1, 0, pos, 1);
int s = (r2 - r1 + 1) * (c4 - c3 + 1);
if (pos + 1 == s) {
ans++;
pos++;
} else {
pos = s - 1;
}
}
return ans;
}
