#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 1000010;
class SegmentTree
{
public:
int getLeft(int node) { return 2*node; }
int getRight(int node) { return 2*node + 1; }
void refresh(int node, int l, int r)
{
int lz[] = { lazy[node][0] , lazy[node][1] };
lazy[node][0] = lazy[node][1] = 0;
for(int i = 0 ; i < 2 ; i++)
mn[node][i] += lz[i];
if( l == r ) return;
for(int i = 0 ; i < 2 ; i++)
{
lazy[ getLeft(node) ][i] += lz[i];
lazy[ getRight(node) ][i] += lz[i];
}
}
void merge(int node, int idLeft, int idRight)
{
qtd[node] = 0;
pii L = { mn[idLeft][0] , mn[idLeft][1] };
pii R = { mn[idRight][0] , mn[idRight][1] };
if( L <= R )
{
mn[node][0] = L.first;
mn[node][1] = L.second;
qtd[node] += qtd[idLeft];
}
if( R <= L )
{
mn[node][0] = R.first;
mn[node][1] = R.second;
qtd[node] += qtd[idRight];
}
}
void build(int node, int l, int r)
{
mn[node][0] = mn[node][1] = 0;
lazy[node][0] = lazy[node][1] = 0;
if( l == r ) return void( qtd[node] = 1 );
int m = ( l + r )/2;
build( getLeft(node) , l , m );
build( getRight(node) , m + 1 , r );
merge( node , getLeft(node) , getRight(node) );
}
void update(int node, int l, int r, int i, int j, int p, int v)
{
if( i > j ) return;
refresh( node , l , r );
if( j < l || r < i ) return;
if( i <= l && r <= j )
{
lazy[node][p] += v;
refresh( node , l , r );
return;
}
int m = ( l + r )/2;
update( getLeft(node) , l , m , i , j , p , v );
update( getRight(node) , m + 1 , r , i , j , p , v );
merge( node , getLeft(node) , getRight(node) );
}
int qtdMin()
{
refresh( 1 , 1 , last );
pii min = { 4 , 0 };
pii root = { mn[1][0] , mn[1][1] };
if( root != min ) return 0;
return qtd[1];
}
void init(int R)
{
last = R;
build( 1 , 1 , last );
}
private:
int last;
int qtd[4*MAXN];
int mn[4*MAXN][2];
int lazy[4*MAXN][2];
};
int n, m;
pii loc[MAXN];
vector< vector<int> > v;
SegmentTree SEG;
void updateSquare(int x, int y, int val)
{
vector< int > aux;
aux.push_back( v[x][y] );
aux.push_back( v[x + 1][y] );
aux.push_back( v[x][y + 1] );
aux.push_back( v[x + 1][y + 1] );
sort( aux.begin() , aux.end() );
SEG.update( 1 , 1 , n*m , aux[0] , aux[1] - 1 , 0 , val );
SEG.update( 1 , 1 , n*m , aux[2] , aux[3] - 1 , 1 , val );
}
void changeSquare(int x, int y, int val)
{
updateSquare( x - 1 , y - 1 , val );
updateSquare( x , y - 1 , val );
updateSquare( x - 1 , y , val );
updateSquare( x , y , val );
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H; m = W;
SEG.init( H*W );
v.resize( n + 2 );
for(int i = 0 ; i <= n + 1 ; i++)
v[i].resize( m + 2 , n*m + 1 );
for(int i = 0 ; i < n*m ; i++)
{
R[i]++; C[i]++;
v[ R[i] ][ C[i] ] = i + 1;
loc[i + 1] = { R[i] , C[i] };
}
for(int i = 0 ; i <= n ; i++)
for(int j = 0 ; j <= m ; j++)
updateSquare( i , j , 1 );
}
int swap_seats(int a, int b)
{
a++; b++;
int xA = loc[a].first;
int yA = loc[a].second;
int xB = loc[b].first;
int yB = loc[b].second;
changeSquare( xA , yA , -1 );
changeSquare( xB , yB , -1 );
swap( loc[a] , loc[b] );
swap( v[xA][yA] , v[xB][yB] );
changeSquare( xA , yA , 1 );
changeSquare( xB , yB , 1 );
return SEG.qtdMin();
}
