#include "seats.h"
#include <bits/stdc++.h>
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int N = (int)1e6 + 6;
const int INF = 0x3f3f3f3f;
struct mnmx {
int mn, mx;
mnmx() {
mn = INF, mx = -INF;
}
};
int get(mnmx a, mnmx b) {
return (a.mx - a.mn + 1) * (b.mx - b.mn + 1);
}
struct subtask12 {
vector <int> posy, posx;
vector <int> id;
int n, m;
bool solution = false;
void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
posy.resize(H * W);
posx.resize(H * W);
n = H, m = W;
for (int i = 0; i < H * W; i++) {
posy[i] = R[i];
posx[i] = C[i];
}
}
int swap_seats(int a, int b) {
swap(posy[a], posy[b]);
swap(posx[a], posx[b]);
mnmx R, C;
int ans = 0;
for (int i = 0; i < n * m; i++) {
chkmin(R.mn, posy[i]);
chkmax(R.mx, posy[i]);
chkmin(C.mn, posx[i]);
chkmax(C.mx, posx[i]);
if (get(R, C) == i + 1) {
ans++;
}
}
return ans;
}
} small;
struct subtask5 {
bool solution = false;
struct node {
int mn, cnt;
node(int x) {
mn = x, cnt = 1;
}
node() {
mn = INF, cnt = 0;
}
node operator + (const node& other) {
node res;
res.mn = min(mn, other.mn);
res.cnt = 0;
if (res.mn == mn) res.cnt += cnt;
if (res.mn == other.mn) res.cnt += other.cnt;
return res;
}
};
node tree[4 * N];
int add[4 * N];
int pos[N], arr[N];
int n;
void push(int v, int tl, int tr) {
if (add[v] == 0) {
return;
}
tree[v].mn += add[v];
if (tl != tr) {
add[v + v + 1] += add[v];
add[v + v + 2] += add[v];
}
add[v] = 0;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = node(tl);
return;
}
int mid = (tl + tr) >> 1;
build(v + v + 1, tl, mid);
build(v + v + 2, mid + 1, tr);
tree[v] = tree[v + v + 1] + tree[v + v + 2];
}
void upd(int ql, int qr, int val, int v, int tl, int tr) {
push(v, tl, tr);
if (ql > tr || tl > qr) {
return;
}
if (ql <= tl && tr <= qr) {
add[v] += val;
push(v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
upd(ql, qr, val, v + v + 1, tl, mid);
upd(ql, qr, val, v + v + 2, mid + 1, tr);
tree[v] = tree[v + v + 1] + tree[v + v + 2];
}
int get(int pos, int v, int tl, int tr) {
push(v, tl, tr);
if (tl == tr) {
return tree[v].mn;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
return get(pos, v + v + 1, tl, mid);
}
else {
return get(pos, v + v + 2, mid + 1, tr);
}
}
void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
assert(H == 1);
n = W;
for (int i = 0; i < n; i++) {
pos[i] = C[i];
}
for (int i = 0; i < n; i++) {
arr[pos[i]] = i;
}
build(0, 0, n - 1);
for (int i = 0; i + 1 < n; i++) {
int mx = max(arr[i], arr[i + 1]);
upd(mx, n - 1, -1, 0, 0, n - 1);
}
}
int swap_seats(int a, int b) {
set <pair<int, int>> go;
if (pos[a] > 0) {
go.insert({ pos[a] - 1, pos[a] });
}
if (pos[a] + 1 < n) {
go.insert({ pos[a], pos[a] + 1 });
}
if (pos[b] > 0) {
go.insert({ pos[b] - 1, pos[b] });
}
if (pos[b] + 1 < n) {
go.insert({ pos[b], pos[b] + 1 });
}
for (pii pr : go) {
int mx = max(arr[pr.fr], arr[pr.sc]);
upd(mx, n - 1, 1, 0, 0, n - 1);
}
swap(arr[pos[a]], arr[pos[b]]);
swap(pos[a], pos[b]);
for (pii pr : go) {
int mx = max(arr[pr.fr], arr[pr.sc]);
upd(mx, n - 1, -1, 0, 0, n - 1);
}
return tree[0].cnt;
}
} line;
void give_initial_chart(int H, int W, vector <int> R, vector <int> C) {
if (H == 1) {
line.solution = true;
line.give_initial_chart(H, W, R, C);
}
else {
small.solution = true;
small.give_initial_chart(H, W, R, C);
}
}
int swap_seats(int a, int b) {
if (line.solution) {
return line.swap_seats(a, b);
}
if (small.solution) {
return small.swap_seats(a, b);
}
}
