#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 1e6 + 5;
int n, m, N, delta[lim], lazy[lim << 2];
pair<int, int>st[lim << 2];
vector<vector<int>>mat;
vector<int>r, c;
void build(int id, int l, int r){
st[id] = make_pair(lazy[id] = 0, r - l + 1);
if(l == r){
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
}
void propagate(int id, int x){
st[id].first += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
pair<int, int>merge(pair<int, int>a, pair<int, int>b){
if(a.first > b.first){
swap(a, b);
}
else if(a.first == b.first){
a.second += b.second;
}
return a;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
int calc_delta(int i){
if(i == 0){
return 0;
}
int cnt_1 = 0, cnt_3 = 0;
for(int ir = 0; ir < 2; ir++){
for(int ic = 0; ic < 2; ic++){
int cur = 0;
for(int iir = 0; iir < 2; iir++){
for(int iic = 0; iic < 2; iic++){
int nr = r[i] - 1 + ir + iir, nc = c[i] - 1 + ic + iic;
if(nr < 0 || nr >= n || nc < 0 || nc >= m || mat[nr][nc] > i){
cur++;
}
}
}
if(cur == 1){
cnt_1++;
}
else if(cur == 2){
cnt_1--;
}
else if(cur == 3){
cnt_3++;
}
else{
cnt_3--;
}
}
}
return cnt_1 + cnt_3;
}
void update_delta(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= m || mat[x][y] == 0){
return;
}
int i = mat[x][y], temp = delta[i];
update(1, 0, N - 1, i, N - 1, (delta[i] = calc_delta(i)) - temp);
}
void give_initial_chart(int _H, int _W, vector<int>_R, vector<int>_C){
swap(r, _R);
swap(c, _C);
build(1, 0, (N = (n = _H) * (m = _W)) - 1);
mat.resize(n, vector<int>(m));
for(int i = 0; i < N; i++){
mat[r[i]][c[i]] = i;
}
memset(delta, 0, sizeof(delta));
for(int i = 1; i < N; i++){
update_delta(r[i], c[i]);
}
}
int swap_seats(int a, int b){
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
for(int i = -1; i < 2; i++){
for(int j = -1; j < 2; j++){
update_delta(r[a] + i, c[a] + j);
update_delta(r[b] + i, c[b] + j);
}
}
return st[1].second;
}
