#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1000010;
vector<pair<int,int>> pos(0);
vector<pair<int,int>> seg(4*MAXN,{0,1});
vector<int> wow(4*MAXN);
vector<vector<int>> haha(0);
int h,w;
pair<int,int> dude(pair<int,int> a, pair<int,int> b) {
if(a.first < b.first) {
return a;
}
else if(a.first > b.first) {
return b;
}
else {
return {a.first,a.second+b.second};
}
}
pair<int,int> calc(int l, int r, int x, int ql, int qr) {
if(l >= ql && r <= qr) {
return seg[x];
}
if(l > qr || r < ql) {
return {INT_MAX,0};
}
int mid = (l+r)/2;
pair<int,int> a = calc(l,mid,x*2,ql,qr);
pair<int,int> b = calc(mid+1,r,x*2+1,ql,qr);
pair<int,int> ans;
ans = dude(a,b);
return {ans.first+wow[x],ans.second};
}
void upd(int l, int r, int x, int ql, int qr, int z) {
if(l >= ql && r <= qr) {
wow[x]+=z;
seg[x] = {seg[x].first+z,seg[x].second};
return;
}
if(l > qr || r < ql) {
return;
}
int mid = (l+r)/2;
upd(l,mid,x*2,ql,qr,z);
upd(mid+1,r,x*2+1,ql,qr,z);
seg[x] = dude(seg[x*2],seg[x*2+1]);
seg[x] = {wow[x]+seg[x].first,seg[x].second};
}
void bro(int x, int y, int z) {
int a,b,c,d;
if(x > 0 && y > 0) {
a = haha[x-1][y-1];
}
else {
a = INT_MAX;
}
if(x > 0 && y < w) {
b = haha[x-1][y];
}
else {
b = INT_MAX;
}
if(x < h && y < w) {
c = haha[x][y];
}
else {
c = INT_MAX;
}
if(x < h && y > 0) {
d = haha[x][y-1];
}
else {
d = INT_MAX;
}
int wut[4] = {a,b,c,d};
sort(wut,wut+4);
if(wut[1] == INT_MAX) {
upd(0,n-1,1,wut[0],n,z);
}
else if(wut[2] == INT_MAX) {
upd(0,n-1,1,wut[0],wut[1]-1,z);
}
else {
upd(0,n-1,1,wut[0],wut[1]-1,z);
upd(0,n-1,1,wut[2],wut[3]-1,z);
if(max(a,c) < min(b,d) || max(b,d) < min(a,c)) {
upd(0,n-1,1,wut[1],wut[2]-1,z);
}
}
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
h = H;
w = W;
n = h*w;
vector<int> wut(w);
for(int i = 0; i < h; i++) {
haha.push_back(wut);
}
for(int i = 0; i < n; i++) {
pos.push_back({r[i],c[i]});
haha[r[i]][c[i]] = i;
}
for(int i = 0; i <= h; i++) {
for(int j = 0; j <= w; j++) {
bro(i,j,1);
}
}
}
int swap_seats(int a, int b) {
vector<pair<int,int>> yo(0);
int a1 = pos[a].first,a2 = pos[a].second,b1 = pos[b].first,b2 = pos[b].second;
yo.push_back({a1,a2});
yo.push_back({a1+1,a2});
yo.push_back({a1,a2+1});
yo.push_back({a1+1,a2+1});
yo.push_back({b1,b2});
yo.push_back({b1+1,b2});
yo.push_back({b1,b2+1});
yo.push_back({b1+1,b2+1});
sort(yo.begin(),yo.end());
vector<pair<int,int>> banana(0);
for(int i = 0; i < yo.size(); i++) {
if(i == 0 || yo[i] != yo[i-1]) {
banana.push_back(yo[i]);
}
}
for(pair<int,int> v: banana) {
bro(v.first,v.second,-1);
}
swap(haha[a1][a2],haha[b1][b2]);
swap(pos[a],pos[b]);
for(pair<int,int> v: banana) {
bro(v.first,v.second,1);
}
return seg[1].second;
}
