#include <bits/stdc++.h>
using namespace std ;
#define fi first
#define se second
#define mid (l+r)/2
#define le node*2
#define ri node*2+1
typedef vector < int > vi ;
typedef pair < int , int > pi ;
#include "seats.h"
int n , m ;
vi a [10009] ;
pi id [1000009] ;
vi tree [2][10009] ;
void upd ( int node , int l , int r , int t , int who , int id , int val ) {
if ( l == r ) {
tree [t][who][node] = val ;
return ;
}
if ( id <= mid ) upd ( le , l , mid , t , who , id , val ) ;
else upd ( ri , mid + 1 , r , t , who , id , val ) ;
tree [t][who][node] = max ( tree [t][who][le] , tree [t][who][ri] ) ;
}
int query ( int node , int l , int r , int t , int who , int s , int e ) {
if ( s > r || e < l ) return -1e9 ;
if ( s <= l && e >= r ) return tree [t][who][node] ;
return max ( query ( le , l , mid , t , who , s , e ) , query ( ri , mid + 1 , r , t ,who , s , e ) ) ;
}
int Mx ( int r1 , int r2 , int c1 , int c2 ) {
if ( r1 > r2 ) swap ( r1 , r2 ) ;
if ( c1 > c2 ) swap ( c1 , c2 ) ;
if ( r1 < 0 || r2 >= n || c1 < 0 || c2 >= m ) return 1e9 ;
int mx = 0 ;
if ( r1 == r2 ) {
mx = query ( 1 , 0 , m-1 , 0 , r1 , c1 , c2 ) ;
}
if ( c1 == c2 ) {
mx = query ( 1 , 0 , n-1 , 1 , c1 , r1 , r2 ) ;
}
return mx ;
}
int solve () {
int r1 , c1 , r2 , c2 , crnt = 0 , ans = 0 ;
r1 = r2 = id [0].fi ;
c1 = c2 = id [0].se ;
while ( 1 ) {
ans += ( crnt == ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) - 1 ) ;
int val1 = Mx ( r1 - 1 , r1 - 1 , c1 , c2 ) ;
int val2 = Mx ( r1 , r2 , c2 + 1 , c2 + 1 ) ;
int val3 = Mx ( r2 + 1 , r2 + 1 , c1 , c2 ) ;
int val4 = Mx ( r1 , r2 , c1 - 1 , c1 - 1 ) ;
int best = min ( min ( val1 , val2 ) , min ( val3 , val4 ) ) ;
if ( best == 1e9 ) break ;
if ( best == val1 ) {
r1 -- ;
crnt = max ( crnt , val1 ) ;
continue ;
}
if ( best == val2 ) {
c2 ++ ;
crnt = max ( crnt , val2 ) ;
continue ;
}
if ( best == val3 ) {
r2 ++ ;
crnt = max ( crnt , val3 ) ;
continue ;
}
if ( best == val4 ) {
c1 -- ;
crnt = max ( crnt , val4 ) ;
continue ;
}
}
return ans ;
}
void give_initial_chart ( int H , int W , vi R, vi C) {
n = H , m = W ;
for ( int i = 0 ; i < n ; i ++ ) {
a [i] .resize (m) ;
}
for ( int i = 0 ; i < n * m ; i ++ ) {
a [R[i]][C[i]] = i ;
id [i] = { R [i] , C [i] } ;
}
for ( int i = 0 ; i < n ; i ++ ) {
tree [0][i] .resize ( 4*m , 0 ) ;
}
for ( int i = 0 ; i < m ; i ++ ) {
tree [1][i] .resize ( 4*n , 0 ) ;
}
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) {
upd ( 1 , 0 , m-1 , 0 , i , j , a [i][j] ) ;
}
}
for ( int j = 0 ; j < m ; j ++ ) {
for ( int i = 0 ; i < n ; i ++ ) {
upd ( 1 , 0 , n-1 , 1 , j , i , a [i][j] ) ;
}
}
}
int swap_seats ( int x , int y ) {
upd ( 1 , 0 , m-1 , 0 , id [x].fi , id [x].se , y ) ;
upd ( 1 , 0 , n-1 , 1 , id [x].se , id [x].fi , y ) ;
upd ( 1 , 0 , m-1 , 0 , id [y].fi , id [y].se , x ) ;
upd ( 1 , 0 , n-1 , 1 , id [y].se , id [y].fi , x ) ;
swap ( id [x] , id [y] ) ;
return solve () ;
}
