#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;
vector<vector<int>> M;
int Min[4040404], Cnt[4040404];
int S[1010101], lazy[4040404];
int R[1010101], C[1010101];
void init(int id, int s, int e){
if (s == e){
Min[id] = S[s];
Cnt[id] = 1;
return;
}
int mid = (s+e)/2;
init(id*2, s, mid);
init(id*2+1, mid+1, e);
Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}
void update(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s) return;
if (ts <= s && e <= te){
Min[id] += v;
lazy[id] += v;
return;
}
Min[id*2] += lazy[id];
Min[id*2+1] += lazy[id];
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
int mid = (s+e)/2;
update(id*2, s, mid, ts, te, v);
update(id*2+1, mid+1, e, ts, te, v);
Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
H=h, W=w;
M.reserve(H+2);
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++){
vector<int> t;
t.push_back(M[i][j]); t.push_back(M[i][j+1]);
t.push_back(M[i+1][j]); t.push_back(M[i+1][j+1]);
sort(t.begin(), t.end());
S[t[0]]++, S[t[1]]--;
S[t[2]]++, S[t[3]]--;
}
for (int i=1; i<=H*W; i++) S[i] += S[i-1];
init(1, 1, H*W);
}
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, v);
update(1, 1, H*W, t[2], t[3]-1, v);
}
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(M[R[a]][C[a]], M[R[b]][C[b]]);
swap(R[a], R[b]);
swap(C[a], C[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];
}
