#include <bits/stdc++.h>
#include "seats.h"
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int H, W;
int R[1010101];
int C[1010101];
vector<vector<int>> M;
pii CV[4040404], lazy[4040404];
int cnt[4040404];
void init(int id, int s, int e){
cnt[id] = e-s+1;
if (s == e) return;
int mid = (s+e)/2;
init(id*2, s, mid);
init(id*2+1, mid+1, e);
}
pii operator+(pii a, pii b){
return pii(a.first+b.first, a.second+b.second);
}
void update(int id, int s, int e, int ts, int te, pii cv){
if (e < ts || te < s) return;
if (ts <= s && e <= te){
CV[id] = CV[id] + cv;
lazy[id] = lazy[id] + cv;
return;
}
int mid = (s+e)/2;
CV[id*2] = CV[id*2] + lazy[id];
CV[id*2+1] = CV[id*2+1] + lazy[id];
lazy[id*2] = lazy[id*2] + lazy[id], lazy[id*2+1] = lazy[id*2+1] + lazy[id];
lazy[id] = pii(0, 0);
update(id*2, s, mid, ts, te, cv);
update(id*2+1, mid+1, e, ts, te, cv);
if (CV[id*2] < CV[id*2+1]) CV[id] = CV[id*2], cnt[id] = cnt[id*2];
else if (CV[id*2] > CV[id*2+1]) CV[id] = CV[id*2+1], cnt[id] = cnt[id*2+1];
else CV[id] = CV[id*2], cnt[id] = cnt[id*2] + cnt[id*2+1];
}
void angle(int x, int y, int v){
vector<int> t;
t.push_back(M[x][y]); t.push_back(M[x][y+1]);
t.push_back(M[x+1][y]); t.push_back(M[x+1][y+1]);
sort(t.begin(), t.end());
update(1, 1, H*W, t[0], t[1]-1, pii(v, 0));
if ((t[0] == M[x][y] && t[1] == M[x+1][y+1]) || (t[1] == M[x][y] && t[0] == M[x+1][y+1])
|| (t[0] == M[x+1][y] && t[1] == M[x][y+1]) || (t[1] == M[x+1][y] && t[0] == M[x][y+1])){
update(1, 1, H*W, t[1], t[2]-1, pii(0, 2*v));
}
update(1, 1, H*W, t[2], t[3]-1, pii(0, v));
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
H=h, W=w;
M.reserve(H+2);
init(1, 1, H*W);
for (int i=0; i<=H+1; i++) M[i].reserve(W+2);
for (int i=0; i<=W+1; i++) M[0][i] = M[H+1][i] = H*W+1;
for (int i=0; i<=H+1; i++) M[i][0] = M[i][W+1] = H*W+1;
for (int i=1; i<=H*W; i++){
R[i] = r[i-1]+1, C[i] = c[i-1]+1;
M[R[i]][C[i]] = i;
}
for (int i=0; i<=H; i++) for (int j=0; j<=W; j++) {
angle(i, j, 1);
}
}
int swap_seats(int a, int b) {
a++, b++;
angle(R[a]-1, C[a]-1, -1);
angle(R[a], C[a]-1, -1);
angle(R[a]-1, C[a], -1);
angle(R[a], C[a], -1);
angle(R[b]-1, C[b]-1, -1);
angle(R[b], C[b]-1, -1);
angle(R[b]-1, C[b], -1);
angle(R[b], C[b], -1);
swap(R[a], R[b]); swap(C[a], C[b]);
M[R[a]][C[a]] = a;
M[R[b]][C[b]] = b;
angle(R[a]-1, C[a]-1, 1);
angle(R[a], C[a]-1, 1);
angle(R[a]-1, C[a], 1);
angle(R[a], C[a], 1);
angle(R[b]-1, C[b]-1, 1);
angle(R[b], C[b]-1, 1);
angle(R[b]-1, C[b], 1);
angle(R[b], C[b], 1);
return cnt[1];
}
