#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int M = (int)1e6 + 10;
int cur;
int pi[M], pj[M];
vector<vector<int>> tt;
struct Node{
int val;
int cnt;
int lazy;
};
Node T[M * 4 + 512];
void push(int node, int cl, int cr){
T[node].val += T[node].lazy;
if(cl != cr){
T[node * 2].lazy += T[node].lazy;
T[node * 2 + 1].lazy += T[node].lazy;
}
T[node].lazy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, int x){
push(node, cl, cr);
if(cr < tl || cl > tr || tl > tr) return;
if(cl >= tl && cr <= tr){
T[node].lazy = x;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, x);
upd(node * 2 + 1, mid + 1, cr, tl, tr, x);
if(T[node * 2].val == T[node * 2 + 1].val){
T[node].val = T[node * 2].val;
T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}
else if(T[node * 2].val < T[node * 2 + 1].val){
T[node].val = T[node * 2].val;
T[node].cnt = T[node * 2].cnt;
}
else{
T[node].val = T[node * 2 + 1].val;
T[node].cnt = T[node * 2 + 1].cnt;
}
}
void upd_rect(int i, int j, int v){
vector<int> tc;
for(int p = 0; p < 2; p ++ ){
for(int q = 0; q < 2; q ++ ){
tc.push_back(tt[i + p][j + q]);
}
}
sort(tc.begin(), tc.end());
upd(1, 0, cur - 1, tc[0], tc[1] - 1, v);
upd(1, 0, cur - 1, tc[2], tc[3] - 1, 4 * v);
}
void build(int node, int cl, int cr){
if(cl == cr){
T[node].cnt = 1;
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
cur = H * W;
tt.resize(H + 2);
for(int i = 0 ; i <= H + 1;i ++ )
tt[i].resize(W + 2, cur);
for(int i = 0 ; i < cur ;i ++ ){
R[i] ++ ;
C[i] ++ ;
pi[i] = R[i];
pj[i] = C[i];
tt[R[i]][C[i]] = i;
}
build(1, 0, cur - 1);
for(int i = 0 ; i <= H; i ++ ){
for(int j = 0 ; j <= W; j ++ ){
upd_rect(i, j, +1);
}
}
}
int swap_seats(int a, int b) {
vector<pii> imp;
for(int i = -1; i <= 0; i ++ ){
for(int j = -1; j <= 0 ; j ++ ){
imp.push_back(mp(pi[a] + i, pj[a] + j));
imp.push_back(mp(pi[b] + i, pj[b] + j));
}
}
sort(imp.begin(), imp.end());
imp.resize(unique(imp.begin(), imp.end()) - imp.begin());
for(auto x : imp)
upd_rect(x.fi, x.se, -1);
swap(tt[pi[a]][pj[a]], tt[pi[b]][pj[b]]);
swap(pi[a], pi[b]);
swap(pj[a], pj[b]);
for(auto x : imp)
upd_rect(x.fi, x.se, +1);
return T[1].cnt;
}
