// M
#include<bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int LG = 20;
struct RMQ
{
vector < int > rmq[LG], mxq[LG], Log;
inline void Init(vector < int > A)
{
rmq[0] = A;
mxq[0] = A;
int n = (int)A.size();
for (int j = 1; j < LG && (1 << j) <= n; j ++)
{
rmq[j] = mxq[j] = vector < int > (n);
for (int i = 0; i + (1 << j) <= n; i ++)
{
rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
mxq[j][i] = max(mxq[j - 1][i], mxq[j - 1][i + (1 << (j - 1))]);
}
}
Log = vector < int > (n + 5, 0);
for (int i = 2; i < n + 5; i ++)
Log[i] = Log[i >> 1] + 1;
}
inline int GetMin(int l, int r)
{
int lg = Log[r - l];
return min(rmq[lg][l], rmq[lg][r - (1 << lg)]);
}
inline int GetMax(int l, int r)
{
int lg = Log[r - l];
return max(mxq[lg][l], mxq[lg][r - (1 << lg)]);
}
};
const int MXN = 1e6 + 10, N = 1009;
int n, m, R[MXN], C[MXN];
vector < vector < int > > A;
RMQ Row[N], Col[N];
inline void BuildRow(int r)
{
vector < int > TMp;
for (int j = 0; j < m; j ++)
TMp.push_back(A[r][j]);
Row[r].Init(TMp);
}
inline void BuildCol(int c)
{
vector < int > TMp;
for (int i = 0; i < n; i ++)
TMp.push_back(A[i][c]);
Col[c].Init(TMp);
}
inline int Calc()
{
int Mx = 0, Cnt = 1;
int lrow = R[0], rrow = R[0], lcol = C[0], rcol = C[0];
while (true)
{
int mnl, mnr, mnu, mnd;
mnl = mnr = mnu = mnd = INT_MAX;
if (lrow > 0)
mnu = Row[lrow - 1].GetMin(lcol, rcol + 1);
if (rrow + 1 < n)
mnd = Row[rrow + 1].GetMin(lcol, rcol + 1);
if (lcol > 0)
mnl = Col[lcol - 1].GetMin(lrow, rrow + 1);
if (rcol + 1 < m)
mnr = Col[rcol + 1].GetMin(lrow, rrow + 1);
int mn = min({mnl, mnr, mnu, mnd});
if (mn == INT_MAX)
break;
if (mn == mnl)
lcol --, Mx = max(Mx, Col[lcol].GetMax(lrow, rrow + 1));
else if (mn == mnr)
rcol ++, Mx = max(Mx, Col[rcol].GetMax(lrow, rrow + 1));
else if (mn == mnu)
lrow --, Mx = max(Mx, Row[lrow].GetMax(lcol, rcol + 1));
else if (mn == mnd)
rrow ++, Mx = max(Mx, Row[rrow].GetMax(lcol, rcol + 1));
//printf("%d , %d :: %d , %d === %d :: %d\n", lrow, rrow, lcol, rcol, Mx, (rrow - lrow + 1) * (rcol - lcol + 1));
if (Mx == (rrow - lrow + 1) * (rcol - lcol + 1) - 1)
Cnt ++;
}
return Cnt;
}
namespace Subtask4
{
int mnl[MXN], mnr[MXN], mnu[MXN], mnd[MXN], CntRs;
inline void Init()
{
CntRs = 1;
mnl[0] = mnr[0] = C[0];
mnu[0] = mnd[0] = R[0];
for (int i = 1; i < n * m; i ++)
{
mnl[i] = min(mnl[i - 1], C[i]);
mnr[i] = max(mnr[i - 1], C[i]);
mnu[i] = min(mnu[i - 1], R[i]);
mnd[i] = max(mnd[i - 1], R[i]);
if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
CntRs ++;
}
}
inline int Swap(int a, int b)
{
if (a > b)
swap(a, b);
for (int i = a; i <= b; i ++)
{
if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
CntRs --;
mnl[i] = i ? mnl[i - 1] : INT_MAX;
mnr[i] = i ? mnr[i - 1] : INT_MIN;
mnu[i] = i ? mnu[i - 1] : INT_MAX;
mnd[i] = i ? mnd[i - 1] : INT_MIN;
mnl[i] = min(mnl[i], C[i]);
mnr[i] = max(mnr[i], C[i]);
mnu[i] = min(mnu[i], R[i]);
mnd[i] = max(mnd[i], R[i]);
if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
CntRs ++;
}
return CntRs;
}
}
int SUB4 = 0;
void give_initial_chart(int _H, int _W, vector < int > _R, vector < int > _C)
{
n = _H; m = _W;
for (int i = 0; i < n * m; i ++)
R[i] = _R[i], C[i] = _C[i];
for (int i = 0; i < n; i ++)
A.pb(vector < int > (m, 0));
for (int i = 0; i < n * m; i ++)
A[R[i]][C[i]] = i;
if (n > 1000 || m > 1000)
{
Subtask4::Init();
SUB4 = 1;
return ;
}
for (int i = 0; i < n; i ++)
BuildRow(i);
for (int j = 0; j < m; j ++)
BuildCol(j);
}
int swap_seats(int a, int b)
{
swap(R[a], R[b]);
swap(C[a], C[b]);
swap(A[R[a]][C[a]], A[R[b]][C[b]]);
if (SUB4)
return Subtask4::Swap(a, b);
BuildRow(R[a]);
BuildRow(R[b]);
BuildCol(C[a]);
BuildCol(C[b]);
return Calc();
}
