#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 is segment tree
static ii tree[2000005]; ///we store the minimum element, and the number of occurances
static long long lazy[2000005]; ///we store the minimum element, and the number of occurances


///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);
  }
}


void prop(int i){
  if(i != 1) prop(i >> 1);
  tree[i<<1].first += lazy[i];
  lazy[i<<1] += lazy[i];
  tree[i<<1|1].first += lazy[i];
  lazy[i<<1|1] += lazy[i];
  lazy[i] = 0;
}

inline int query(){
  prop((n) >> 1); ///propogate the 2 ends
  prop((2*n-1) >> 1);

  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

    //cout << values[0] << " " << values[1] << " " << 1 << "\n";
    //cout << values[2] << " " << values[3] << " " << "f" << "\n";
  }
}

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];
  //cout << aPos.first << " " << aPos.second << "\n";
  //cout << bPos.first << " " << bPos.second << "\n";

  ///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();
}