#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Seg{
vector<pair<int, int>> seg;
vector<int> lazy;
int cap;
pair<int, int> combine(pair<int, int> a, pair<int, int> b){
if(a > b) swap(a, b);
if(a.first == b.first) a.second += b.second;
return a;
}
void init(vector<int> v){
int n = (int)v.size();
for(int i = 1; i < n; i++) v[i] += v[i-1];
for(cap = 1; cap < n; cap*=2);
seg.resize(2*cap, {INF, 1});
lazy.resize(2*cap, 0);
for(int i = 0; i < n; i++) seg[i+cap].first = v[i];
for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
}
void apply(int v, int i){
seg[i].first += v;
lazy[i] += v;
}
void push(int i){
apply(lazy[i], 2*i);
apply(lazy[i], 2*i+1);
lazy[i] = 0;
}
void upd(int l, int r, int v, int a, int b, int i){
if(l <= a && b <= r) apply(v, i);
else if(b < l || r < a) return;
else{
push(i);
int m = (a+b)/2;
upd(l, r, v, a, m, 2*i);
upd(l, r, v, m+1, b, 2*i+1);
seg[i] = combine(seg[2*i], seg[2*i+1]);
}
}
void upd(int l, int r, int v){upd(l, r, v, 1, cap, 1);}
};
int n, W, H;
vector<int> r, c;
vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
vector<vector<int>> num;
vector<int> adj;
Seg seg;
int calc(int x, int y){
int res = 0;
for(int i = -1; i < 1; i++){
for(int j = -1; j < 1; j++){
int cnt = 0;
for(int a = 0; a < 2; a++){
for(int b = 0; b < 2; b++){
int nx = x+i+a;
int ny = y+j+b;
if(num[nx][ny] <= num[x][y]) cnt++;
}
}
if(cnt == 1) res++;
if(cnt == 2) res--;
if(cnt == 3) res++;
if(cnt == 4) res--;
}
}
return res;
}
void upd(int x, int y){
if(x == 0 || x == H+1 || y == 0 || y == W+1) return;
int res = calc(x, y);
seg.upd(num[x][y]+1, n+1, res-adj[num[x][y]]);
adj[num[x][y]] = res;
}
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
H = h, W = w;
n = H*W;
r = R;
c = C;
num.assign(H+2, vector<int>(W+2, INF));
adj.resize(n);
for(int i = 0; i < n; i++) num[r[i]+1][c[i]+1] = i;
for(int i = 0; i < n; i++){
int x = r[i]+1, y = c[i]+1;
adj[i] = calc(x, y);
}
seg.init(adj);
}
int qry = 0;
int swap_seats(int a, int b) {
qry++;
if(a > b) swap(a, b);
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(num[r[a]+1][c[a]+1], num[r[b]+1][c[b]+1]);
for(int i = -1; i <= 1; i++){
for(int j = -1; j <= 1; j++){
upd(r[a]+1+i, c[a]+1+j);
upd(r[b]+1+i, c[b]+1+j);
}
}
int ans = seg.seg[1].second;
return ans;
}
