#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
vector<int> linha1(maxn, maxn), linha2(maxn, -maxn), coluna1(maxn, maxn), coluna2(maxn, -maxn), marc(maxn);
vector<int> i, j;
int n, m;
int resp;
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;
if( n <= 1000 && m <= 1000 ) for( int k = 0; k < n*m; k++ ) update( 1, 0, n*m - 1, k, i[k], j[k] );
else{
for( int k = 1; k <= H*W; k++ ){
linha1[k] = min(linha1[k - 1], i[k - 1] );
linha2[k] = max(linha2[k - 1], i[k - 1] );
coluna1[k] = min(coluna1[k - 1], j[k - 1] );
coluna2[k] = max(coluna2[k - 1], j[k - 1] );
if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; }
}
}
}
int swap_seats(int a, int b) {
swap( i[a], i[b] ); swap( j[a], j[b] );
if( n <= 1000 && m <= 1000 ){
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 ans = 0;
while( cur < n*m ){
Node aux = query( 1, 0, n*m - 1, 0, cur );
if( aux.area() == cur + 1 ){
ans++; cur++;
}
else{
cur = aux.area() - 1;
}
}
return ans;
}
for( int k = min(a, b) + 1; k <= max(a, b) + 1; k++ ){
if( marc[k] ){ marc[k] = 0; resp--; }
linha1[k] = min(linha1[k - 1], i[k - 1] );
linha2[k] = max(linha2[k - 1], i[k - 1] );
coluna1[k] = min(coluna1[k - 1], j[k - 1] );
coluna2[k] = max(coluna2[k - 1], j[k - 1] );
if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; }
}
return resp;
}
