#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 , n , m , crnt ;
int a [1000009] , b [1000009] ;
pair < pi , pi > tree [4000009] ;
pair < pi , pi > merge ( pair < pi ,pi > x , pair < pi , pi > y ) {
pair < pi , pi > ret ;
ret .fi.fi = min ( x .fi.fi , y .fi.fi ) ;
ret .fi.se = max ( x .fi.se , y .fi.se ) ;
ret .se.fi = min ( x .se.fi , y .se.fi ) ;
ret .se.se = max ( x .se.se , y .se.se ) ;
return ret ;
}
void upd ( int node , int l , int r , int id ) {
if ( l == r ) {
tree [node] = { { a [l] , a [l] } , { b [l] , b [l] } } ;
return ;
}
if ( id <= mid ) upd ( le , l , mid , id ) ;
else upd ( ri , mid + 1 , r , id ) ;
tree [node] = merge ( tree [le] , tree [ri] ) ;
}
pair < pi , pi > query ( int node , int l , int r , int s , int e ) {
if ( s > r || e < l ) return { { 1e9 , 0 } , { 1e9 , 0 } } ;
if ( s <= l && e >= r ) return tree [node] ;
return merge ( query ( le , l , mid , s , e ) , query ( ri , mid + 1 , r , s , e ) ) ;
}
void give_initial_chart ( int H , int W , vi R, vi C ) {
n = H , m = W , N = n * m ;
for ( int i = 0 ; i < N ; i ++ ) {
a [i] = R [i] ;
b [i] = C [i] ;
upd ( 1 , 0 , N -1 , i ) ;
}
}
int swap_seats ( int x , int y ) {
swap ( a [x] , a [y] ) ;
swap ( b [x] , b [y] ) ;
upd ( 1 , 0 , N - 1 , x ) ;
upd ( 1 , 0 , N - 1 , y ) ;
int r1 = 1e9 , r2 = 0 , c1 = 1e9 , c2 = 0 , ans = 0 ;
for ( int i = 0 ; i < N ; i ++ ) {
r1 = min ( r1 , a [i] ) ;
r2 = max ( r2 , a [i] ) ;
c1 = min ( c1 , b [i] ) ;
c2 = max ( c2 , b [i] ) ;
if ( ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) == i + 1 ) {
ans ++ ;
continue ;
}
int to = ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) - 1 ;
pair < pi , pi > info = query ( 1 , 0 , N -1 , i , to ) ;
r1 = min ( r1 , info .fi.fi ) ;
r2 = max ( r2 , info .fi.se ) ;
c1 = min ( c1 , info .se.fi ) ;
c2 = max ( c2 , info .se.se ) ;
i = to - 1 ;
}
return ans ;
}
