#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
typedef pair<long long, int> ii;
int n, rows, cols;
static ii pos[1000005]; ///for each number, ii(r, c)
static vector<vector<int> > arr; ///arr[r*cols+c] is the element at (r,c)
///we build a grid such that the boundaries are filled with the number n
///Everything here onwards is segment tree
///This is a range min range add segment tree, but we also store the no. of occurances of the minimum element
static ii tree[2000005]; ///we store the minimum element, and the number of occurances
static long long lazy[2000005];
///helper function to update the value of node i from the children of i
inline void relax(int i){
if(tree[i<<1].first == tree[i<<1|1].first){
tree[i] = ii(tree[i<<1].first+lazy[i], tree[i<<1].second + tree[i<<1|1].second);
}
else{
tree[i] = min(tree[i<<1],tree[i<<1|1]);
tree[i].first += lazy[i];
}
}
void initSegment(){
for(int i = n;i < 2 * n;i++) tree[i] = ii(0,1);
for(int i = n - 1;i >= 0;i--) relax(i);
}
inline void update(int l, int r, long long v){
if(l == r) return;
int ll = l + n, rr = r - 1 + n;
for(l += n,r += n;l < r;l>>=1,r>>=1){
if(l&1){
tree[l].first += v;
lazy[l] += v;
l++;
}
if(r&1){
r--;
tree[r].first += v;
lazy[r] += v;
}
}
while(ll > 1){
ll >>= 1;
relax(ll);
}
while(rr > 1){
rr >>= 1;
relax(rr);
}
}
inline int query(){
if(tree[1].first+lazy[1] == 4){
return tree[1].second;
}
else{
return 0;
}
}
///segment tree ends
///consider a 2x2 square whose top-left corner is at r, c
void makeUpdate(int r, int c, bool isUndo){
vector<int> values = {arr[r][c],arr[r+1][c],arr[r][c+1],arr[r+1][c+1]};
sort(values.begin(),values.end());
///if isReverse, we undo our previous update
if(isUndo){
update(values[0],values[1],-1);
update(values[2],values[3],-inf);
}
else{
update(values[0],values[1],1); ///add one to imply within that range, there is one more 2x2 square with exactly 1 black square
update(values[2],values[3],inf); ///add infinity to "ruin" that range. When there are 2 black squares in the 2x2 square, it's impossible to have beautiful rectangle
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
rows = H; cols = W;
for(int i = 0;i < rows+2;i++){
arr.push_back({});
arr.back().assign(cols+2,n);
}
for(int i = 0;i < n;i++){
R[i]++; C[i]++;
arr[R[i]][C[i]] = i;
pos[i] = ii(R[i],C[i]);
}
initSegment();
for(int r = 0;r <= rows;r++){
for(int c = 0;c <= cols;c++){
makeUpdate(r,c,false);
}
}
}
int swap_seats(int a, int b) {
ii aPos = pos[a]; ii bPos = pos[b];
///undo updates for all affected rectangles
makeUpdate(aPos.first-1,aPos.second-1,true);
makeUpdate(aPos.first,aPos.second-1,true);
makeUpdate(aPos.first-1,aPos.second,true);
makeUpdate(aPos.first,aPos.second,true);
makeUpdate(bPos.first-1,bPos.second-1,true);
makeUpdate(bPos.first,bPos.second-1,true);
makeUpdate(bPos.first-1,bPos.second,true);
makeUpdate(bPos.first,bPos.second,true);
///swapping the elements
pos[b] = aPos; pos[a] = bPos;
arr[aPos.first][aPos.second] = b; arr[bPos.first][bPos.second] = a;
///now update again for all affected rectangles
makeUpdate(aPos.first-1,aPos.second-1,false);
makeUpdate(aPos.first,aPos.second-1,false);
makeUpdate(aPos.first-1,aPos.second,false);
makeUpdate(aPos.first,aPos.second,false);
makeUpdate(bPos.first-1,bPos.second-1,false);
makeUpdate(bPos.first,bPos.second-1,false);
makeUpdate(bPos.first-1,bPos.second,false);
makeUpdate(bPos.first,bPos.second,false);
return query();
}
