#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const int inf = (int)1e9;
int n,m;
vector<vector<int>> f(N);
array<int,2> pos[N];
ll t[N * 4],add[N * 4];
int c[N * 4];
void build(int v = 1,int tl = 0,int tr = n * m - 1){
c[v] = (tr - tl + 1);
if(tl == tr) return;
int tm = (tl + tr) >>1;
build(v+v,tl,tm);
build(v+v+1,tm+1,tr);
}
void inc(int v,ll val){
t[v] += val;
add[v] += val;
}
void push(int v){
if(add[v]&&v + v+1 < N *4){
inc(v+v,add[v]);
inc(v+v+1,add[v]);
add[v] = 0;
}
}
void upd(int l,int r,int val,int v = 1,int tl = 0,int tr = n * m - 1){
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r){
inc(v,val);
}else{
push(v);
int tm = (tl + tr) >> 1;
upd(l,r,val,v+v,tl,tm);
upd(l,r,val,v+v+1,tm+1,tr);
t[v] = min(t[v + v],t[v + v + 1]);
c[v] = (t[v +v] == t[v] ? c[v +v] : 0) + (t[v + v + 1] == t[v] ? c[v + v + 1] : 0);
}
}
int get(int pos,int v = 1,int tl =0,int tr = n * m - 1){
if(tl == tr) return t[v];
push(v);
int tm = (tl + tr) >> 1;
if(pos <= tm) return get(pos,v+v,tl,tm);
return get(pos,v+v+1,tm+1,tr);
}
int q(int x,int y){
if(min(x,y) < 0 || x >= n || y >=m) return inf;
return f[x][y];
}
void ad(int x,int y){
vector<int> c = {q(x,y),q(x+1,y),q(x,y+1),q(x+1,y+1)};
sort(c.begin(),c.end());
if(c[0] != inf){
upd(c[0],c[1] - 1,1);
}
if(c[2] != inf){
upd(c[2],c[3] - 1,inf);
}
}
void del(int x,int y){
vector<int> c = {q(x,y),q(x+1,y),q(x,y+1),q(x+1,y+1)};
sort(c.begin(),c.end());
if(c[0] != inf){
upd(c[0],c[1] - 1,-1);
}
if(c[2] != inf){
upd(c[2],c[3] - 1,-inf);
}
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C){
n = H;
m = W;
build();
for(int i = 0;i < n;i++){
f[i].resize(m + 1);
}
for(int i = 0;i < n * m;i++){
f[R[i]][C[i]] = i;
pos[i] = {R[i],C[i]};
}
for(int i = -1;i < n;i++){
for(int j = -1;j < m;j++){
ad(i,j);
}
}
}
void ad1(int x,int y){
ad(x,y);
ad(x-1,y);
ad(x,y-1);
ad(x-1,y-1);
}
void del1(int x,int y){
del(x,y);
del(x-1,y);
del(x,y-1);
del(x-1,y-1);
}
int swap_seats(int a, int b){
array<int,2> x = pos[a];
array<int,2> y = pos[b];
del1(x[0],x[1]);
del1(y[0],y[1]);
swap(f[x[0]][x[1]],f[y[0]][y[1]]);
ad1(x[0],x[1]);
ad1(y[0],y[1]);
swap(pos[a],pos[b]);
// cout << get(0) << "x\n";
// cout << "______________________\n";
return c[1];
}
