#include "seats.h"
#include <bits/stdc++.h>
#define vi vector < int >
using namespace std;
int N, M, tot, aux;
vector < int > R, C, LR, RR, UC, LC, ans;
void give_initial_chart ( int _h, int _w, vi _r, vi _c )
{
N = _h;
M = _w;
R = _r;
C = _c;
LR.resize ( N * M );
RR.resize ( N * M );
UC.resize ( N * M );
LC.resize ( N * M );
ans.resize ( N * M );
LR[0] = R[0];
RR[0] = R[0];
UC[0] = C[0];
LC[0] = C[0];
ans[0] = 1, tot = 1;
for ( int i = 1; i < N * M; i++ )
{
LR[i] = min ( LR[i - 1], R[i] );
RR[i] = max ( RR[i - 1], R[i] );
UC[i] = min ( UC[i - 1], C[i] );
LC[i] = max ( LC[i - 1], C[i] );
if ( (RR[i] - LR[i] + 1) * (LC[i] - UC[i] + 1) == i + 1 )
ans[i] = 1, tot++;
}
}
int swap_seats ( int a, int b )
{
aux = R[a];
R[a] = R[b];
R[b] = aux;
aux = C[a];
C[a] = C[b];
C[b] = aux;
tot -= ans[a], ans[a] = 0;
if ( a > 0 )
{
LR[a] = min ( LR[a - 1], R[a] );
RR[a] = max ( RR[a - 1], R[a] );
UC[a] = min ( UC[a - 1], C[a] );
LC[a] = max ( LC[a - 1], C[a] );
}
else
{
LR[0] = R[0];
RR[0] = R[0];
UC[0] = C[0];
LC[0] = C[0];
}
ans[a] = 1, tot++;
for ( int i = a + 1; i <= b; i++ )
{
tot -= ans[i], ans[i] = 0;
LR[i] = min ( LR[i - 1], R[i] );
RR[i] = max ( RR[i - 1], R[i] );
UC[i] = min ( UC[i - 1], C[i] );
LC[i] = max ( LC[i - 1], C[i] );
if ( (RR[i] - LR[i] + 1) * (LC[i] - UC[i] + 1) == i + 1 )
ans[i] = 1, tot++;
}
return tot;
}
