#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
using namespace std;
int N, H, W, maximR[MAXN], minimR[MAXN], maximC[MAXN], minimC[MAXN], ans;
int STrow[2*MAXN + 5][2], STcol[2*MAXN + 5][2], last;
vector <int> R, C;
int maxR, minR, maxC, minC;
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;
N = H * W;
swap ( R, _r );
swap ( C, _c );
if ( H <= 1000 && W <= 1000 )
{
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 ();
}
else
{
maximR[0] = R[0];
minimR[0] = R[0];
maximC[0] = C[0];
minimC[0] = C[0];
ans++;
for ( int i = 1; i < H * W; i++ )
{
maximR[i] = max ( maximR[i - 1], R[i] );
minimR[i] = min ( minimR[i - 1], R[i] );
maximC[i] = max ( maximC[i - 1], C[i] );
minimC[i] = min ( minimC[i - 1], C[i] );
if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
ans++;
}
}
}
int swap_seats ( int a, int b )
{
if ( H <= 1000 && W <= 1000 )
{
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] );
maxR = -1, minR = INF;
maxC = -1, minC = INF;
ans = 0, last = 0;
for ( int i = 0; i < H * W; )
{
maxR = max ( maxR, qryrow ( last, i, 0 ) );
minR = min ( minR, qryrow ( last, i, 1 ) );
maxC = max ( maxC, qrycol ( last, i, 0 ) );
minC = min ( minC, qrycol ( last, i, 1 ) );
last = i;
if ( (maxR - minR + 1) * (maxC - minC + 1) == i + 1 )
ans++;
if ( (maxR - minR + 1) * (maxC - minC + 1) > i + 1 )
i = (maxR - minR + 1) * (maxC - minC + 1) - 1;
else
i++;
}
}
else
{
swap ( R[a], R[b] );
swap ( C[a], C[b] );
if ( a > b )
swap ( a, b );
for ( int i = a; i <= b; i++ )
{
if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
ans--;
if ( i == 0 )
{
maximR[0] = R[0];
minimR[0] = R[0];
maximC[0] = C[0];
minimC[0] = C[0];
}
else
{
maximR[i] = max ( maximR[i - 1], R[i] );
minimR[i] = min ( minimR[i - 1], R[i] );
maximC[i] = max ( maximC[i - 1], C[i] );
minimC[i] = min ( minimC[i - 1], C[i] );
}
if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
ans++;
}
}
return ans;
}
