#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int N, M;
int A[MAXN];
int X[MAXN];
int Y[MAXN];
int P[MAXN];
bool B[3][3];
struct segment {
int L, R;
int val, ans, lazy;
segment *lef, *rig;
void build(int x,int y) {
L=x;
R=y;
val=0;
ans=R-L+1;
lazy=0;
if (x==y) {
return;
}
int T;
T=(L+R)/2;
lef=new segment;
lef->build(L,T);
rig=new segment;
rig->build(T+1,R);
return;
}
void balance() {
if (!lazy) {
return;
}
lef->val+=lazy;
lef->lazy+=lazy;
rig->val+=lazy;
rig->lazy+=lazy;
lazy=0;
return;
}
void update(int x,int y,int z) {
if (L>y||R<x||!z) {
return;
}
if (L>=x&&R<=y) {
val+=z;
lazy+=z;
return;
}
balance();
lef->update(x,y,z);
rig->update(x,y,z);
val=min(lef->val,rig->val);
ans=0;
if (val==lef->val) {
ans+=lef->ans;
}
if (val==rig->val) {
ans+=rig->ans;
}
return;
}
void debug() {
return;
if (L==R) {
cout<<val<<' ';
if (R==N*M-1) {
cout<<'\n';
}
return;
}
balance();
lef->debug();
rig->debug();
}
}
dt;
int pos(int a,int b) {
if (a<0||a>=N||b<0||b>=M) {
return N*M;
}
return A[a*M+b];
}
int index(int a) {
return X[a]*M+Y[a];
}
bool valid(bool a,bool b,bool c) {
return (a^b)&&(b^c);
}
int score() {
int ret=0;
ret+=valid(B[0][1],B[1][1],B[1][0]);
ret+=valid(B[0][1],B[1][1],B[1][2]);
ret+=valid(B[2][1],B[1][1],B[1][0]);
ret+=valid(B[2][1],B[1][1],B[1][2]);
ret+=valid(B[0][0],B[0][1],B[1][1]);
ret+=valid(B[0][0],B[1][0],B[1][1]);
ret+=valid(B[0][2],B[0][1],B[1][1]);
ret+=valid(B[0][2],B[1][2],B[1][1]);
ret+=valid(B[2][0],B[2][1],B[1][1]);
ret+=valid(B[2][0],B[1][0],B[1][1]);
ret+=valid(B[2][2],B[2][1],B[1][1]);
ret+=valid(B[2][2],B[1][2],B[1][1]);
return ret;
}
void balance(int a) {
if (a==N*M) {
return;
}
for (int i=-1;i<=1;i++) {
for (int j=-1;j<=1;j++) {
B[i+1][j+1]=pos(X[a]+i,Y[a]+j)<a;
}
}
int save;
save=score();
B[1][1]=1;
save=score()-save;
if (save!=P[a]) {
dt.update(a,N*M-1,save-P[a]);
P[a]=save;
}
}
void spread(int a) {
for (int i=-1;i<=1;i++) {
for (int j=-1;j<=1;j++) {
balance(pos(X[a]+i,Y[a]+j));
}
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
N=H;
M=W;
dt.build(0,N*M-1);
for (int i=0;i<N*M;i++) {
X[i]=R[i];
Y[i]=C[i];
A[index(i)]=i;
}
for (int i=0;i<N*M;i++) {
balance(i);
}
}
int swap_seats(int a, int b) {
swap(X[a],X[b]);
swap(Y[a],Y[b]);
swap(A[index(a)],A[index(b)]);
spread(a);
spread(b);
return dt.ans;
}
