#include <bits/stdc++.h>
#include "seats.h"
#define debug
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 1e6+10 ;
const int inf=1e9+10 ;
using namespace std ;
struct Seg
{
pii v[MAXN] ;
int m(int l, int r) { return (l+r)/2 ; }
pii merge( pii x , pii y ) { return mk( min(x.ff, y.ff) , max(x.ss,y.ss) ) ; }
void upd(int pos, int l, int r, int x , int val)
{
if(l==r)
{
v[pos] = mk(val,val) ;
return ;
}
if( x <= m(l,r) ) upd(pos*2, l, m(l,r) , x , val) ;
else upd(pos*2+1, m(l,r)+1 , r , x , val) ;
v[pos] = merge( v[pos*2] , v[pos*2+1] ) ;
}
pii query( int pos , int l , int r , int en )
{
if( l > en ) return mk( inf , -inf ) ;
if( r <= en ) return v[pos] ;
pii al = query(pos*2, l , m(l,r) , en) ;
pii ar = query(pos*2+1, m(l,r)+1 , r ,en ) ;
return merge(al,ar) ;
}
void print(int pos, int l, int r)
{
debug("%d %d -> %d %d\n" , l , r , v[pos].ff ,v[pos].ss) ;
if(l==r) return ;
print(pos*2,l,m(l,r)) ;
print(pos*2+1,m(l,r)+1,r) ;
}
} ;
int n ;
pii p[MAXN] ;
Seg r , c ;
// ------------------------------------
int swap_seats(int a , int b )
{
swap(p[a] , p[b] ) ;
r.upd( 1,0,n-1,a,p[a].ff ) ;
r.upd(1,0,n-1,b,p[b].ff) ;
c.upd(1,0,n-1,a,p[a].ss) ;
c.upd( 1 , 0, n-1 , b , p[b].ss ) ;
int ans = 0 ;
lp(i,0,n)
{
debug("My ans is %d and now I'm at %d\n" , ans , i ) ;
pii curAux , curMin , curMax ;
curAux = r.query( 1 , 0 , n-1 , i ) ;
curMin.ff = curAux.ff ;
curMax.ff = curAux.ss ;
curAux = c.query(1,0,n-1,i) ;
curMin.ss = curAux.ff ;
curMax.ss = curAux.ss ;
int grid = ( curMax.ff - curMin.ff + 1 ) * ( curMax.ss - curMin.ss + 1 ) ;
if( grid == i+1 ) ans ++ ;
else i = grid-2 ;
}
return ans ;
}
void give_initial_chart(int h , int w , vector<int> R , vector<int> C )
{
n = R.size() ;
lp(i,0,n) p[i] = mk( R[i] , C[i] ) ;
lp(i,0,n)
{
r.upd( 1 , 0 , n-1 , i , p[i].ff ) ;
c.upd(1,0,n-1,i,p[i].ss) ;
}
r.print(1,0,n-1) ;
printf("\n") ;
c.print(1,0,n-1) ;
}
