#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define mn first
#define cnt second
ii merge(ii& a, ii& b) {
if(a.mn < b.mn) return a;
if(a.mn > b.mn) return b;
return {a.mn, a.cnt + b.cnt};
}
struct node {
int b, e;
ii fn;
int lz = 0;
node *lc, *rc;
node(int b, int e) : b(b), e(e) {}
node(vi& a, int b, int e) : b(b), e(e) {
if(b == e) {
fn = {a[b], 1};
} else {
int m = (b + e) >> 1;
lc = new node(a, b, m);
rc = new node(a, m+1, e);
fn = merge(lc -> fn, rc -> fn);
}
}
void apply(int val) {
fn.mn += val, lz += val;
}
void push() {
if(b < e) {
lc -> apply(lz);
rc -> apply(lz);
} lz = 0;
}
void update(int x, int y, int inc) {
if(b > y or e < x) return;
if(x <= b and e <= y) {
apply(inc);
return;
}
if(lz) push();
lc -> update(x, y, inc);
rc -> update(x, y, inc);
fn = merge(lc -> fn, rc -> fn);
}
};
typedef node* pnode;
const int maxn = 1e6 + 6;
int R[maxn], C[maxn], n, m, N;
vi a;
vi wot;
pnode root = nullptr;
int delta(int i) {
int c = C[i], ret = 0;
ret += (!c or wot[c-1] > i) ? 1 : -1;
ret += (c+1 == N or wot[c+1] > i) ? 1 : -1;
return ret;
}
void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) {
n = H, m = W, N = n*m;
wot.resize(N);
for(int i = 0; i < N; ++i) {
::R[i] = RR[i], ::C[i] = CC[i];
wot[::C[i]] = i;
}
a.resize(N);
for(int i = 0; i < N; ++i) {
a[i] = delta(i);
if(i) a[i] += a[i-1];
}
root = new node(a, 0, N-1);
for(int i = N-1; i >= 1; --i) {
a[i] -= a[i-1];
}
}
void replace(int i, int x) {
root -> update(i, N-1, x - a[i]);
a[i] = x;
}
int swap_seats(int p, int q) {
swap(wot[C[p]], wot[C[q]]);
swap(C[p], C[q]);
p = C[p], q = C[q];
for(int x : {p-1, p, p+1, q-1, q, q+1}) {
if(0 <= x && x < N) {
replace(wot[x], delta(wot[x]));
}
}
return root -> fn.cnt;
}
