#include "seats.h"
#include <iostream>
using namespace std;
const int N = 1e6+10;
const int inf = 1e9;
struct node
{
int mn;
int st_mn;
int prsm;
node() : mn(2), st_mn(1), prsm(0) { }
};
int n = 0;
node sg[4*N];
int lz[4*N];
int pr2[4*N];
int delta[4*N];
int poz[N];
int vre[N];
node create(int vr)
{
node rez;
rez.mn = rez.prsm = vr;
rez.st_mn=1;
return rez;
}
node join(node l, node r)
{
node rez;
if (l.mn == r.mn+l.prsm)
{
rez.mn = l.mn;
rez.st_mn = l.st_mn+r.st_mn;
rez.prsm = l.prsm+r.prsm;
}
else if (l.mn < r.mn+l.prsm)
{
rez.mn = l.mn;
rez.st_mn = l.st_mn;
rez.prsm = l.prsm+r.prsm;
}
else
{
rez.mn = r.mn;
rez.st_mn = r.st_mn;
rez.prsm = r.prsm+r.prsm;
}
return rez;
}
void build(int v, int l, int r)
{
if (l+1==r)
{
sg[v] = create(delta[l]);
return;
}
int md = (l+r)/2;
build(v*2+1, l, md);
build(v*2+2, md, r);
sg[v] = join(sg[v*2+1], sg[v*2+2]);
}
void upd(int v, int l, int r, int i)
{
if (l+1 == r)
{
sg[v] = create(delta[i]);
return;
}
int md = (l+r)/2;
if (i < md)
upd(v*2+1, l, md, i);
else
upd(v*2+2, md, r, i);
sg[v] = join(sg[v*2+1], sg[v*2+2]);
}
int calc_delta(int vr)
{
int ix = poz[vr];
int dl = 0;
dl += ((ix==0 || vre[ix-1]>vr) ? 1 : -1);
dl += ((ix==n-1 || vre[ix+1]>vr) ? 1 : -1);
return dl;
}
void upd_delta(int ix)
{
if (ix<0||ix>=n)
return;
int vr = vre[ix];
delta[vr] = calc_delta(vr);
upd(0, 0, n, vr);
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c)
{
n=H*W;
if (H!=1)
exit(0);
for (int i = 0; i < n; i++)
{
poz[i] = c[i];
vre[poz[i]]=i;
}
for (int i = 0; i < n; i++)
delta[i] = calc_delta(i);
build(0, 0, n);
}
int swap_seats(int a, int b)
{
swap(vre[poz[a]], vre[poz[b]]);
swap(poz[a], poz[b]);
upd_delta(poz[a]-1); upd_delta(poz[b]-1);
upd_delta(poz[a]); upd_delta(poz[b]);
upd_delta(poz[a]+1); upd_delta(poz[b]+1);
return sg[0].st_mn;
}
