#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
#define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2
using namespace std;
int H, W, STrow[4 * MAXN][2], STcol[4 * MAXN][2];
vector <int> R, C;
int maximR, minimR, maximC, minimC, ans;
void buildrow ( int node = 0, int l = 0, int r = H*W - 1 )
{
if ( l == r )
{
STrow[node][0] = R[l];
STrow[node][1] = R[l];
return;
}
VARS;
buildrow ( lchild, l, mid );
buildrow ( rchild, mid + 1, r );
STrow[node][0] = max ( STrow[lchild][0], STrow[rchild][0] );
STrow[node][1] = min ( STrow[lchild][1], STrow[rchild][1] );
}
void buildcol ( int node = 0, int l = 0, int r = H*W - 1 )
{
if ( l == r )
{
STcol[node][0] = C[l];
STcol[node][1] = C[l];
return;
}
VARS;
buildcol ( lchild, l, mid );
buildcol ( rchild, mid + 1, r );
STcol[node][0] = max ( STcol[lchild][0], STcol[rchild][0] );
STcol[node][1] = min ( STcol[lchild][1], STcol[rchild][1] );
}
int qryrow ( int L, int R, bool f, int node = 0, int l = 0, int r = H*W - 1 )
{
if ( r < L or R < l )
return (!f ? -1 : INF);
if ( L <= l && r <= R )
return STrow[node][f];
VARS;
if ( !f )
return max ( qryrow ( L, R, f, lchild, l, mid ), qryrow ( L, R, f, rchild, mid + 1, r ) );
else
return min ( qryrow ( L, R, f, lchild, l, mid ), qryrow ( L, R, f, rchild, mid + 1, r ) );
}
int qrycol ( int L, int R, bool f, int node = 0, int l = 0, int r = H*W - 1 )
{
if ( r < L or R < l )
return (!f ? -1 : INF);
if ( L <= l && r <= R )
return STcol[node][f];
VARS;
if ( !f )
return max ( qrycol ( L, R, f, lchild, l, mid ), qrycol ( L, R, f, rchild, mid + 1, r ) );
else
return min ( qrycol ( L, R, f, lchild, l, mid ), qrycol ( L, R, f, rchild, mid + 1, r ) );
}
void updrow ( int pos, int x, int node = 0, int l = 0, int r = H*W - 1 )
{
if ( r < pos or pos < l )
return;
if ( l == r )
{
STrow[node][0] = x;
STrow[node][1] = x;
return;
}
VARS;
updrow ( pos, x, lchild, l, mid );
updrow ( pos, x, rchild, mid + 1, r );
STrow[node][0] = max ( STrow[lchild][0], STrow[rchild][0] );
STrow[node][1] = min ( STrow[lchild][1], STrow[rchild][1] );
}
void updcol ( int pos, int x, int node = 0, int l = 0, int r = H*W - 1 )
{
if ( r < pos or pos < l )
return;
if ( l == r )
{
STcol[node][0] = x;
STcol[node][1] = x;
return;
}
VARS;
updcol ( pos, x, lchild, l, mid );
updcol ( pos, x, rchild, mid + 1, r );
STcol[node][0] = max ( STcol[lchild][0], STcol[rchild][0] );
STcol[node][1] = min ( STcol[lchild][1], STcol[rchild][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 );
buildrow ();
buildcol ();
}
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;
}
