#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#include "seats.h"
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int N = 4000000 + 11;
pi t[4*N];
int lazy[4*N];
pi pos[4*N];
int tot, n, m;
vector<vector<int>>a;
pi merge(pi a, pi b){
if(a.ff < b.ff)return a;
if(a.ff > b.ff)return b;
return {a.ff, a.ss + b.ss};
}
void push(int v){
if(!lazy[v])return;
t[2*v].ff += lazy[v];
t[2*v + 1].ff += lazy[v];
lazy[2*v] += lazy[v];
lazy[2*v + 1] += lazy[v];
lazy[v] = 0;
}
void build(int v, int l, int r){
if(l == r){
t[v] = {0, 1};
return;
}
int mid = (l + r) >> 1;
build(2*v, l, mid);
build(2*v + 1, mid + 1, r);
t[v] = merge(t[2*v], t[2*v + 1]);
}
void update(int v, int tl, int tr, int l, int r, int add){
push(v);
if(tl > r || tr < l)return;
if(l <= tl && tr <= r){
lazy[v] += add;
t[v].ff += add;
push(v);
return;
}
int mid = (l + r) >> 1;
if(l <= mid)update(2*v, tl, mid, l, r, add);
if(r > mid)update(2*v + 1, mid + 1, tr, l, r, add);
push(v);
t[v] = merge(t[2*v], t[2*v + 1]);
}
bool ok(pi x){
if(x.ff > 0 && x.ff <= n){
if(x.ss > 0 && x.ss <= m){
return 1;
}
}
return 0;
}
pi getB(pi x){
int l = a[x.ff][x.ss];
int r = tot + 1;
for(int i = 0; i < 4; i++){
pi A = x;
A.ff += dx[i];
A.ss += dy[i];
if(ok(A)){
if(i < 2)r = min(r, a[x.ff][x.ss]);
}
}
return {l, r};
}
int secondSmallestNeighbour(pi x){
vector<int>s;
for(int i = 0; i < 4; i++){
pi A = x;
A.ff += dx[i];
A.ss += dy[i];
if(ok(A)){
s.push_back(a[A.ff][A.ss]);
}
}
sort(all(s));
if(sz(s) > 1)return s[1];
return tot + 1;
}
void deleteA(pi x){
int l = secondSmallestNeighbour(x);
int r = a[x.ff][x.ss];
if(r > l){
update(1, 1, tot, l, r - 1, -1);
}
}
void updateA(pi x){
int l = secondSmallestNeighbour(x);
int r = a[x.ff][x.ss];
if(r > l){
update(1, 1, tot, l, r - 1, +1);
}
}
void deleteB(pi x){
pi p = getB(x);
if(p.ss > p.ff){
update(1, 1, tot, p.ff, p.ss - 1, -1);
}
}
void updateB(pi x){
pi p = getB(x);
if(p.ss > p.ff){
update(1, 1, tot, p.ff, p.ss - 1, +1);
}
}
void rewrite(pi x, int val){
deleteA(x);
for(int i = 0; i < 4; i++){
pi A = x;
A.ff += dx[i];
A.ss += dy[i];
if(ok(A)){
deleteA(A);
}
}
deleteB(x);
for(int i = 2; i < 4; i++){
pi A = x;
A.ff += dx[i];
A.ss += dy[i];
if(ok(A)){
deleteB(A);
}
}
a[x.ff][x.ss] = val;
updateA(x);
for(int i = 0; i < 4; i++){
pi A = x;
A.ff += dx[i];
A.ss += dy[i];
if(ok(A)){
updateA(A);
}
}
updateB(x);
for(int i = 2; i < 4; i++){
pi A = x;
x.ff += dx[i];
x.ss += dy[i];
if(ok(A)){
updateB(A);
}
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
m = W;
n = H;
tot = n*m;
build(1, 1, tot);
a = vector<vector<int>>(n + 5, vector<int>(m + 5, 0));
for(int i = 0 ; i < n*m; i++){
a[R[i] + 1][C[i] + 1] = i + 1;
pos[i] = {R[i] + 1, C[i] + 1};
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
updateA({i, j}); //first condition
updateB({i, j}); //second condition
}
}
}
int swap_seats(int A, int B) {
rewrite(pos[A], B + 1);
rewrite(pos[B], A + 1);
swap(pos[A], pos[B]);
return (t[1].ff == 1 ? t[1].ss : 0);
}
