#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int nm, n, m, T[N][3], delta[N];
vector<array<int, 2>> pos;
vector<vi> grid;
void build(int l, int r, int k){
if(l == r){
T[k][0] = delta[l];
T[k][1] = 1;
T[k][2] = delta[l];
return;
}
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
if(T[k<<1][0] < T[k<<1|1][0] + T[k<<1][2]){
T[k][0] = T[k<<1][0];
T[k][1] = T[k<<1][1];
}else if(T[k<<1|1][0] + T[k<<1][2] < T[k<<1][0]){
T[k][0] = T[k<<1|1][0] + T[k<<1][2];
T[k][1] = T[k<<1|1][1];
}else{
T[k][0] = T[k<<1][0];
T[k][1] = T[k<<1][1] + T[k<<1|1][1];
}
T[k][2] = T[k<<1][2] + T[k<<1|1][2];
}
void upd(int l, int r, int p, int k){
if(l == r){
T[k][0] = delta[l];
T[k][1] = 1;
T[k][2] = delta[l];
return;
}
int mid = l+r>>1;
if(p <= mid) upd(l, mid, p, k<<1);
else upd(mid + 1, r, p, k<<1|1);
if(T[k<<1][0] < T[k<<1|1][0] + T[k<<1][2]){
T[k][0] = T[k<<1][0];
T[k][1] = T[k<<1][1];
}else if(T[k<<1|1][0] + T[k<<1][2] < T[k<<1][0]){
T[k][0] = T[k<<1|1][0] + T[k<<1][2];
T[k][1] = T[k<<1|1][1];
}else{
T[k][0] = T[k<<1][0];
T[k][1] = T[k<<1][1] + T[k<<1|1][1];
}
T[k][2] = T[k<<1][2] + T[k<<1|1][2];
}
int get(int x, int y, int k){
if(x < 0 || y < 0 || x >= n || y >= m) return 0;
return grid[x][y] <= k ? 1 : 0;
}
int get_delta(int x, int y, int k){
int score = 0;
for(int i = x - 1; i <= x; ++i){
for(int j = y - 1; j <= y; ++j){
int cnt = get(i, j, k - 1) + get(i + 1, j, k - 1) + get(i, j + 1, k - 1) + get(i + 1, j + 1, k - 1);
int cnt2 = get(i, j, k) + get(i + 1, j, k) + get(i, j + 1, k) + get(i + 1, j + 1, k);
score += (cnt2 == 1) + (cnt2 == 3) - (cnt == 1) - (cnt == 3); // delta
}
}
return score;
}
void give_initial_chart(int nn, int mm, std::vector<int> R, std::vector<int> C) {
n = nn;
m = mm;
nm = n * m;
pos.resize(nm);
grid.resize(n, vi(m));
for(int i = 0; i < nm; ++i){
pos[i] = {R[i], C[i]};
grid[R[i]][C[i]] = i;
}
for(int i =0 ; i < nm; ++i){
delta[i] = get_delta(R[i], C[i], i);
// cerr << delta[i] << ' ';
}
build(0, nm-1, 1);
}
int swap_seats(int a, int b) {
swap(pos[a], pos[b]);
swap(grid[pos[a][0]][pos[a][1]], grid[pos[b][0]][pos[b][1]]);
for(int rep = 0; rep < 2; ++rep){
for(int i = pos[a][0] - 1; i <= pos[a][0] + 1; ++i){
for(int j = pos[a][1] - 1; j <= pos[a][1] + 1; ++j){
if(i < 0 || j < 0 || i >= n || j >= m) continue;
delta[grid[i][j]] = get_delta(i, j, grid[i][j]);
upd(0, nm-1, grid[i][j], 1);
}
}
swap(a, b);
}
// cerr << "upd\n";
// for(int i =0 ; i < nm; ++i){
// cerr << delta[i] << ' ';
// }
// delta[a] = get_delta(pos[a][0], pos[a][1], a);
// delta[b] = get_delta(pos[b][0], pos[b][1], b);
// upd(0, nm-1, a, 1);
// upd(0, nm-1, b, 1);
return (T[1][0] == 4 ? T[1][1] : 0);
}
