#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
int val1,val2,cnt,lazy1,lazy2;
node(){
val1 = 0,val2 = 0,cnt = 1,lazy1 = 0,lazy2 = 0;
}
node(int a){
val1 = 1e9,val2 = 1e9,cnt = 0,lazy1 = 0,lazy2 = 0;
}
};
node merge(node a,node b){
node ret(-1);
ret.val1 = min(a.val1,b.val1);
if(a.val1 == ret.val1)
ret.val2 = min(ret.val2,a.val2);
if(b.val1 == ret.val1)
ret.val2 = min(ret.val2,b.val2);
if(a.val1 == ret.val1 && a.val2 == ret.val2){
ret.cnt += a.cnt;
}
if(b.val1 == ret.val1 && b.val2 == ret.val2){
ret.cnt += b.cnt;
}
return ret;
}
struct SegTree{
vector<node> t;
int n;
void init(int size){
n = size;
t.assign(4*n,node());
}
void push(int v){
t[v*2].val1 += t[v].lazy1;
t[v*2].val2 += t[v].lazy2;
t[v*2].lazy1 += t[v].lazy1;
t[v*2].lazy2 += t[v].lazy2;
t[v*2+1].val1 += t[v].lazy1;
t[v*2+1].val2 += t[v].lazy2;
t[v*2+1].lazy1 += t[v].lazy1;
t[v*2+1].lazy2 += t[v].lazy2;
t[v].lazy1 = t[v].lazy2 = 0;
}
void upd(int v,int tl,int tr,int l,int r,pair<int,int> val){
if(tr < l || r < tl)
return;
if(l <= tl && tr <= r){
t[v].val1 += val.first;
t[v].val2 += val.second;
t[v].lazy1 += val.first;
t[v].lazy2 += val.second;
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return node(-1);
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int l,int r,pair<int,int> val){
if(l > r)return;
upd(1,1,n,l,r,val);
}
void upd(pair<int,int> range,pair<int,int> val){
upd(range.first,range.second,val);
}
node get(int l,int r){
if(l > r)return node(-1);
return get(1,1,n,l,r);
}
};
SegTree tree;
vector<vector<int>> grid;
int n;
vector<int> r,c;
pair<int,int> getw(pair<int,int> a){
return {1,grid[a.first][a.second] - 1};
}
pair<int,int> getb(pair<int,int> a){
return {grid[a.first][a.second], n};
}
pair<int,int> intersect(pair<int,int> a,pair<int,int> b){
return {max(a.first,b.first),min(a.second,b.second)};
}
vector<pair<int,int>> rect(int x,int y){
vector<pair<int,int>> ret;
for(int i = 0;i<=1;i++){
for(int j = 0;j<=1;j++){
ret.push_back({x+i,y+j});
}
}
return ret;
}
void upd1(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getb(points[j]));
}
else range = intersect(range,getw(points[j]));
}
tree.upd(range,{coef,0});
}
}
void upd2(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getw(points[j]));
}
else range = intersect(range,getb(points[j]));
}
tree.upd(range,{0,coef});
}
}
void upd(int x,int y,int coef){
pair<int,int> range;
vector<pair<int,int>> points;
//*.
//..
//xa
//aa
points = rect(x-1,y-1);
upd1(points,coef);
//ax
//aa
points = rect(x-1,y);
upd1(points,coef);
//aa
//xa
points = rect(x,y-1);
upd1(points,coef);
//aa
//ax
points = rect(x,y);
upd1(points,coef);
//.*
//**
//xa
//aa
points = rect(x-1,y-1);
upd2(points,coef);
//ax
//aa
points = rect(x-1,y);
upd2(points,coef);
//aa
//xa
points = rect(x,y-1);
upd2(points,coef);
//aa
//ax
points = rect(x,y);
upd2(points,coef);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
r = R;
c = C;
grid = vector<vector<int>> (H+2,vector<int>(W+2,H*W+1));
tree.init(n);
for(int i = 0;i<n;i++){
r[i]++;
c[i]++;
grid[r[i]][c[i]] = i+1;
// upd(r[i],c[i],1);
// for(int j = 1;j<=n;j++){
// cout << tree.get(j,j).val1 << " " << tree.get(j,j).val2 << " " << tree.get(j,j).cnt << endl;
// }
// cout << endl;
}
for(int i = 0;i<=H;i++){
for(int j = 0;j<=W;j++){
upd1(rect(i,j),1);
upd2(rect(i,j),1);
}
}
// for(int i = 1;i<=n;i++){
// cout << tree.get(i,i).val1 << " " << tree.get(i,i).val2 << " " << tree.get(i,i).cnt << endl;
// }
}
int swap_seats(int a, int b) {
upd(r[a],c[a],-1);
upd(r[b],c[b],-1);
swap(grid[r[a]][c[a]],grid[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
upd(r[a],c[a],1);
upd(r[b],c[b],1);
return tree.get(1,n).cnt;
}
