#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
struct Node{
int minVal, cntMin;
Node(int x = 0, int cnt = 1){
minVal = x;
cntMin = cnt;
}
void update(int x){
minVal += x;
}
Node operator + (const Node &oth){
if (minVal < oth.minVal)
return *this;
if (minVal > oth.minVal)
return oth;
return Node(minVal, cntMin + oth.cntMin);
}
};
struct SegmentTree{
int n;
int lazy[4000007];
Node d[4000007];
void init(int _n){
n = _n;
}
void doLazy(int id, int l, int r){
d[id].update(lazy[id]);
if (l < r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
doLazy(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v){
lazy[id] += val;
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
d[id] = d[id << 1] + d[id << 1 | 1];
}
void update(int pos, int val){
update(1, 0, n - 1, pos, n - 1, val);
}
int getCnt(){
doLazy(1, 0, n - 1);
assert(d[1].minVal == 4);
return d[1].cntMin;
}
} st;
int h, w, tmp[4], nTmp;
vector<vector<int>> chair;
vector<int> x, y;
bool inSide(int x, int y){
return (0 <= x && x < h && 0 <= y && y < w);
}
void UpdateSquare(int x, int y, int type){
nTmp = 0;
for(int dx = 0; dx < 2; dx++)
for(int dy = 0; dy < 2; dy++)
if (inSide(x + dx, y + dy))
tmp[nTmp++] = chair[x + dx][y + dy];
sort(tmp, tmp + nTmp);
for(int i = 0; i < nTmp; i++){
st.update(tmp[i], type);
type *= -1;
}
}
void give_initial_chart(int hh, int ww, vector<int> r, vector<int> c) {
h = hh;
w = ww;
x = r;
y = c;
chair.assign(h, vector<int>(w, 0));
for(int i = 0; i < w * h; i++)
chair[r[i]][c[i]] = i;
st.init(h * w);
for(int i = -1; i < h; i++)
for(int j = -1; j < w; j++)
UpdateSquare(i, j, 1);
}
int swap_seats(int a, int b) {
for(int dx = -1; dx < 1; dx++)
for(int dy = -1; dy < 1; dy++){
UpdateSquare(x[a] + dx, y[a] + dy, -1);
UpdateSquare(x[b] + dx, y[b] + dy, -1);
}
swap(chair[x[a]][y[a]], chair[x[b]][y[b]]);
swap(x[a], x[b]);
swap(y[a], y[b]);
for(int dx = -1; dx < 1; dx++)
for(int dy = -1; dy < 1; dy++){
UpdateSquare(x[a] + dx, y[a] + dy, +1);
UpdateSquare(x[b] + dx, y[b] + dy, +1);
}
return st.getCnt();
}
