#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)
{
if( lazy[node] == 0 ) return;
int lz = lazy[node];
lazy[node] = 0;
mn[node] += lz;
if( l == r ) return;
lazy[ getLeft(node) ] += lz;
lazy[ getRight(node) ] += lz;
}
void merge(int node, int idLeft, int idRight)
{
qtd[node] = 0;
if( mn[idLeft] <= mn[idRight] )
{
mn[node] = mn[idLeft];
qtd[node] += qtd[idLeft];
}
if( mn[idLeft] >= mn[idRight] )
{
mn[node] = mn[idRight];
qtd[node] += qtd[idRight];
}
}
void build(int node, int l, int r)
{
mn[node] = lazy[node] = 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 v)
{
if( i > j ) return;
refresh( node , l , r );
if( j < l || r < i ) return;
if( i <= l && r <= j )
{
lazy[node] += v;
refresh( node , l , r );
return;
}
int m = ( l + r )/2;
update( getLeft(node) , l , m , i , j , v );
update( getRight(node) , m + 1 , r , i , j , v );
merge( node , getLeft(node) , getRight(node) );
}
int qtdMin()
{
refresh( 1 , 1 , last );
if( mn[1] != 4 ) return 0;
return qtd[1];
}
void init(int R)
{
last = R;
build( 1 , 1 , last );
}
private:
int last;
int mn[4*MAXN];
int qtd[4*MAXN];
int lazy[4*MAXN];
};
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 , val );
SEG.update( 1 , 1 , n*m , aux[2] , aux[3] - 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();
}
