#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
using namespace std;
int N, H, W, STrow[2*MAXN + 5][2], STcol[2*MAXN + 5][2];
vector <int> R, C;
int maximR, minimR, maximC, minimC, ans;
void build ( )
{
for ( int i = N - 1; i; i-- )
{
STrow[i][0] = max ( STrow[2*i][0], STrow[2*i + 1][0] );
STrow[i][1] = min ( STrow[2*i][1], STrow[2*i + 1][1] );
STcol[i][0] = max ( STcol[2*i][0], STcol[2*i + 1][0] );
STcol[i][1] = min ( STcol[2*i][1], STcol[2*i + 1][1] );
}
}
int qryrow ( int l, int r, bool f )
{
l += N, r += N;
r++;
int leftRes = (!f ? -1 : INF);
int rightRes = (!f ? -1 : INF);
for ( ; l < r; l /= 2, r /= 2 )
{
if ( f == 0 )
{
if ( l & 1 )
leftRes = max ( leftRes, STrow[l++][f] );
if ( r & 1 )
rightRes = max ( rightRes, STrow[--r][f] );
}
else
{
if ( l & 1 )
leftRes = min ( leftRes, STrow[l++][f] );
if ( r & 1 )
rightRes = min ( rightRes, STrow[--r][f] );
}
}
if ( !f )
return max ( leftRes, rightRes );
else
return min ( leftRes, rightRes );
}
int qrycol ( int l, int r, bool f )
{
l += N, r += N;
r++;
int leftRes = (!f ? -1 : INF);
int rightRes = (!f ? -1 : INF);
for ( ; l < r; l /= 2, r /= 2 )
{
if ( f == 0 )
{
if ( l & 1 )
leftRes = max ( leftRes, STcol[l++][f] );
if ( r & 1 )
rightRes = max ( rightRes, STcol[--r][f] );
}
else
{
if ( l & 1 )
leftRes = min ( leftRes, STcol[l++][f] );
if ( r & 1 )
rightRes = min ( rightRes, STcol[--r][f] );
}
}
if ( !f )
return max ( leftRes, rightRes );
else
return min ( leftRes, rightRes );
}
void updrow ( int pos, int x )
{
STrow[N + pos][0] = x;
STrow[N + pos][1] = x;
for ( int i = (pos + N) / 2; i; i /= 2 )
{
STrow[i][0] = max ( STrow[2*i][0], STrow[2*i + 1][0] );
STrow[i][1] = min ( STrow[2*i][1], STrow[2*i + 1][1] );
}
}
void updcol ( int pos, int x )
{
STcol[N + pos][0] = x;
STcol[N + pos][1] = x;
for ( int i = (pos + N) / 2; i; i /= 2 )
{
STcol[i][0] = max ( STcol[2*i][0], STcol[2*i + 1][0] );
STcol[i][1] = min ( STcol[2*i][1], STcol[2*i + 1][1] );
}
}
void give_initial_chart ( int _h, int _w, vector <int> _r, vector <int> _c )
{
H = _h;
W = _w;
swap ( R, _r );
swap ( C, _c );
N = H * W;
for ( int i = N; i < 2 * N; i++ )
{
STrow[i][0] = R[i - N];
STrow[i][1] = R[i - N];
STcol[i][0] = C[i - N];
STcol[i][1] = C[i - N];
}
build ();
}
int swap_seats ( int a, int b )
{
swap ( R[a], R[b] );
updrow ( a, R[a] );
updrow ( b, R[b] );
swap ( C[a], C[b] );
updcol ( a, C[a] );
updcol ( b, C[b] );
maximR = -1, minimR = INF;
maximC = -1, minimC = INF;
ans = 0;
for ( int i = 0; i < H * W; )
{
maximR = qryrow ( 0, i, 0 );
minimR = qryrow ( 0, i, 1 );
maximC = qrycol ( 0, i, 0 );
minimC = qrycol ( 0, i, 1 );
//cout << i << ", {" << minimR << ", " << maximR << "}, {" << minimC << ", " << maximC << "}\n";
if ( (maximR - minimR + 1) * (maximC - minimC + 1) == i + 1 )
ans++;
if ( (maximR - minimR + 1) * (maximC - minimC + 1) > i + 1 )
i = (maximR - minimR + 1) * (maximC - minimC + 1) - 1;
else
i++;
}
return ans;
}
