#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, j, k) for(int i=j; i<k; i++)
#define pii pair<int, int>
#define f first
#define s second
const int mxN=1e6+5;
int dx[4]={-1, -1, 0, 0}, dy[4]={-1, 0, -1, 0};
pii t[mxN*4];
int tag[mxN*4], n;
vector<vector<int>> v;
vector<int> R;
vector<int> C;
void init(int idx, int l, int r) {
if(l==r) {
t[idx].s=1;
return;
}
int mid=(l+r)/2;
init(idx*2, l, mid);
init(idx*2+1, mid+1, r);
}
void psh(int idx) {
t[idx].f=min(t[idx*2].f, t[idx*2+1].f);
t[idx].s=0;
if(t[idx].f==t[idx*2].f)
t[idx].s+=t[idx*2].s;
if(t[idx].f==t[idx*2+1].f)
t[idx].s+=t[idx*2+1].s;
}
void app(int idx, int val) {
t[idx].f+=val;
tag[idx]+=val;
}
void psd(int idx) {
app(idx*2, tag[idx]);
app(idx*2+1, tag[idx]);
tag[idx]=0;
}
void upd(int idx, int l, int r, int val, int ql, int qr) {
if(l<=ql&&qr<=r) {
t[idx].f+=val;
tag[idx]+=val;
return;
}
psd(idx);
int mid=(ql+qr)/2;
if(l<=mid)
upd(idx*2, l, r, val, ql, mid);
if(mid<r)
upd(idx*2+1, l, r, val, mid+1, qr);
psh(idx);
}
void chg(int x, int y, int val) {
vector<int> vi;
rep(i, 0, 4)
vi.push_back(v[x+dx[i]][y+dy[i]]);
sort(vi.begin(), vi.end());
upd(1, vi[0], vi[1]-1, val, 0, n);
upd(1, vi[2], vi[3]-1, val, 0, n);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
v.resize(H+5, vector<int>(W+5, H*W));
n=H*W-1;
init(1, 0, n);
rep(i, 0, H*W) {
R[i]++;
C[i]++;
v[R[i]][C[i]]=i;
}
::R=R;
::C=C;
rep(i, 1, H+2) {
rep(j, 1, W+2) {
chg(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
rep(i, 0, 4) {
chg(R[a]-dx[i], C[a]-dy[i], -1);
chg(R[b]-dx[i], C[b]-dy[i], -1);
}
swap(v[R[a]][C[a]], v[R[b]][C[b]]);
rep(i, 0, 4) {
chg(R[a]-dx[i], C[a]-dy[i], 1);
chg(R[b]-dx[i], C[b]-dy[i], 1);
}
swap(R[a], R[b]);
swap(C[a], C[b]);
return t[1].s;
}
