#include "seats.h"
#include <cassert>
#include <algorithm>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int INF = 0x3f3f3f3f;
int H, W, N, ans;
std::vector<int> R, C;
//Subtasks 1, 2, 4
std::vector<int> maxr, minr, maxc, minc;
int calc(int u, int v)
{
for(int i=u;i<v;++i)
if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1]))
--ans;
for(int i=u;i<v;++i)
{
minr[i+1]=std::min(minr[i], R[i]);
maxr[i+1]=std::max(maxr[i], R[i]+1);
minc[i+1]=std::min(minc[i], C[i]);
maxc[i+1]=std::max(maxc[i], C[i]+1);
if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1]))
++ans;
}
return ans;
}
//Subtask 3
struct ST
{
public:
std::vector<int> v;
int S;
ST(int _S=0): S(_S), v(_S*4, 0) {}
void init(int _S)
{
S=_S;
v.assign(_S*4, 0);
}
void set(int n, int l, int r, int q, int val)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(q<m) set(n<<1, l, m, q, val);
else set(n<<1|1, m, r, q, val);
v[n]=std::max(v[n<<1], v[n<<1|1]);
}
else v[n]=val;
}
void set(int q, int val) {set(1, 0, S, q, val);}
int qry(int n, int l, int r, int qr)
{
if(r <= qr) return v[n];
if(r-l>1)
{
int m=l+(r-l)/2;
int f=qry(n<<1, l, m, qr);
if(m<qr) ckmax(f, qry(n<<1|1, m, r, qr));
return f;
}
assert(0);
}
int qry(int q) {return qry(1, 0, S, q);}
} mxrst, mnrst, mxcst, mncst;
int st3()
{
int f=0;
int n=1;
for(;n <= N;)
{
int sz = (mxrst.qry(n)+mnrst.qry(n))*(mxcst.qry(n)+mncst.qry(n));
if(sz == n) ++f, ++n;
else n=sz;
}
return f;
}
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
H=_H, W=_W;
R=_R, C=_C;
N = H*W;
if(H <= 1000 && W <= 1000)
{
mxrst.init(N);
mnrst.init(N);
mxcst.init(N);
mncst.init(N);
for(int i=0;i<N;++i)
{
mxrst.set(i, R[i]+1);
mnrst.set(i, -R[i]);
mxcst.set(i, C[i]+1);
mncst.set(i, -C[i]);
}
return;
}
maxr.assign(N+1, -1);
maxc.assign(N+1, -1);
minr.assign(N+1, INF);
minc.assign(N+1, INF);
calc(0, N);
}
int swap_seats(int a, int b) {
std::swap(R[a], R[b]);
std::swap(C[a], C[b]);
if(H <= 1000 && W <= 1000)
{
for(int i:{a,b})
{
mxrst.set(i, R[i]+1);
mnrst.set(i, -R[i]);
mxcst.set(i, C[i]+1);
mncst.set(i, -C[i]);
}
return st3();
}
if(b<a) std::swap(a,b);
return calc(a, b+1);
}
