#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
vector<int> i, j;
int n, m;
struct Node{
int l1, l2, c1, c2; Node( int l1 = maxn, int l2 = -maxn, int c1 = maxn, int c2 = -maxn ) : l1(l1), l2(l2), c1(c1), c2(c2) {}
Node operator + ( Node n ){ return Node( min(l1, n.l1), max(l2, n.l2), min(c1, n.c1), max(c2, n.c2) ); }
int area(){ return (l2 - l1 + 1)*(c2 - c1 + 1); }
} seg[4*maxn];
void update( int pos, int ini, int fim, int id, int a, int b ){
if( ini == fim ){ seg[pos] = Node(a, a, b, b); return; }
int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2;
if( id <= mid ) update( l, ini, mid, id, a, b );
else update( r, mid + 1, fim, id, a, b );
seg[pos] = seg[l] + seg[r];
}
Node query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return seg[0];
if( ki <= ini && fim <= kf ) return seg[pos];
int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2;
return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
i = R; j = C;
n = H, m = W;
for( int k = 0; k < n*m; k++ ) update( 1, 0, n*m - 1, k, i[k], j[k] );
}
int swap_seats(int a, int b) {
swap( i[a], i[b] ); swap( j[a], j[b] );
update( 1, 0, n*m - 1, a, i[a], j[a] );
update( 1, 0, n*m - 1, b, i[b], j[b] );
int cur = 0;
int resp = 0;
while( cur < n*m ){
Node aux = query( 1, 0, n*m - 1, 0, cur );
if( aux.area() == cur + 1 ){
resp++; cur++;
}
else{
cur = aux.area() - 1;
}
}
return resp;
}
