#include "seats.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long
using namespace std;
vector <vector <ll>> A;
ll n, m, dj[4][2] = {{-1, -1}, {-1, 0}, {0, -1}, {0, 0}};
array <ll, 2> X[1000000];
array <ll, 2> comp(array<ll, 2> x, array<ll, 2> y) {
if (x[0] < y[0]) return x;
else if (x[0] > y[0]) return y;
else return {x[0], x[1]+y[1]};
}
array<ll, 4> get_mn(vector <ll> v) {
sort(v.begin(), v.end());
return {v[0], v[1], v[2], v[3]};
}
struct SegTree{
struct Node{
ll mnval = 0;
ll mncnt = 0;
ll lazy = 0;
};
vector <Node> st;
void init() {
st.resize(4*n*m);
build(1, 0, n*m-1);
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id].mncnt = 1;
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id].mncnt = r-l+1;
}
void push(ll id) {
st[id*2].mnval += st[id].lazy, st[id*2].lazy += st[id].lazy;
st[id*2+1].mnval += st[id].lazy, st[id*2+1].lazy += st[id].lazy;
st[id].lazy = 0;
}
void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
st[id].mnval += w, st[id].lazy += w;
return;
}
push(id);
ll mid = (l+r)/2;
update(id*2, l, mid, ql, qr, w);
update(id*2+1, mid+1, r, ql, qr, w);
array <ll, 2> tmp = comp({st[id*2].mnval, st[id*2].mncnt}, {st[id*2+1].mnval, st[id*2+1].mncnt});
st[id] = {tmp[0], tmp[1], 0};
}
void query(ll id, ll l, ll r) {
if (l == r) {
cout << st[id].mnval << " ";
return;
}
push(id);
ll mid = (l+r)/2;
query(id*2, l, mid);
query(id*2+1, mid+1, r);
}
ll ans() {
return st[1].mnval == 4 ? st[1].mncnt : 0;
}
}ST;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H, m = W;
A.resize(n+2);
ST.init();
for (int i=0; i<=n+1; ++i) {
A[i].resize(m+2);
for (int j=0; j<=m+1; ++j) {
A[i][j] = 1e18;
}
}
for (int i=0; i<n*m; ++i) {
X[i] = {R[i]+1, C[i]+1};
A[R[i]+1][C[i]+1] = i;
}
for (int i=0; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
auto [l, r, ul, ur] = get_mn({A[i][j], A[i+1][j], A[i][j+1], A[i+1][j+1]});
ST.update(1, 0, n*m-1, l, n*m-1, 1);
if (r != 1e18) ST.update(1, 0, n*m-1, r, n*m-1, -1);
if (ul != 1e18) ST.update(1, 0, n*m-1, ul, n*m-1, 1e9);
if (ur != 1e18) ST.update(1, 0, n*m-1, ur, n*m-1, -1e9);
}
}
}
void check(ll x, ll y, ll w) {
for (int i=0; i<4; ++i) {
auto xx = x + dj[i][0], yy = y + dj[i][1];
auto [l, r, ul, ur] = get_mn({A[xx][yy], A[xx+1][yy], A[xx][yy+1], A[xx+1][yy+1]});
ST.update(1, 0, n*m-1, l, n*m-1, w);
if (r != 1e18) ST.update(1, 0, n*m-1, r, n*m-1, -w);
if (ul != 1e18) ST.update(1, 0, n*m-1, ul, n*m-1, 1e9*w);
if (ur != 1e18) ST.update(1, 0, n*m-1, ur, n*m-1, -1e9*w);
}
}
int swap_seats(int a, int b) {
check(X[a][0], X[a][1], -1);
check(X[b][0], X[b][1], -1);
swap(A[X[a][0]][X[a][1]], A[X[b][0]][X[b][1]]);
swap(X[a], X[b]);
check(X[a][0], X[a][1], 1);
check(X[b][0], X[b][1], 1);
//ST.query(1, 0, n*m-1);
//cout << endl;
return ST.ans();
}
