#include "seats.h"
#include <stdio.h>
using namespace std;
int N;
int all[1000005];
int what[1000005];
struct A
{
int l,r;
int nxl,nxr;
int small,con;
int add;
}Node[4000005];
int now=1;
void UPD(int here)
{
Node[Node[here].nxl].add+=Node[here].add;
Node[Node[here].nxl].small+=Node[here].add;
Node[Node[here].nxr].add+=Node[here].add;
Node[Node[here].nxr].small+=Node[here].add;
Node[here].add=0;
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].small=0;
Node[here].add=0;
Node[here].con=(r-l+1);
if(l==r) return ;
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
}
void cha(int l,int r,int con,int here)
{
if(Node[here].l==l&&Node[here].r==r)
{
Node[here].add+=con;
Node[here].small+=con;
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxr);
else
{
cha(l,(Node[here].l+Node[here].r)/2,con,here);
cha((Node[here].l+Node[here].r)/2+1,r,con,here);
}
Node[here].con=0;
Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
if(Node[Node[here].nxl].small==Node[here].small) Node[here].con+=Node[Node[here].nxl].con;
if(Node[Node[here].nxr].small==Node[here].small) Node[here].con+=Node[Node[here].nxr].con;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
int i;
N=H*W;
for(i=0;i<N;i++)
{
R[i]++;
C[i]++;
all[i]=C[i];
what[C[i]]=all[i];
}
what[0]=N+1;
what[N+1]=N+1;
build(1,N,0);
for(i=1;i<=N;i++)
{
if(what[i]<what[i-1])
{
//printf("%d %d\n",what[i],what[i-1]-1);
cha(what[i],what[i-1]-1,1,0);
}
if(what[i]<what[i+1])
{
//printf("%d %d\n",what[i],what[i+1]-1);
cha(what[i],what[i+1]-1,1,0);
}
}
}
int swap_seats(int a, int b)
{
int x,y;
x=all[a];
y=all[b];
if(what[x]<what[x-1]) cha(what[x],what[x-1]-1,-1,0);
if(what[x]<what[x+1]) cha(what[x],what[x+1]-1,-1,0);
if(what[y]<what[y-1]) cha(what[y],what[y-1]-1,-1,0);
if(what[y]<what[y+1]) cha(what[y],what[y+1]-1,-1,0);
swap(all[a],all[b]);
swap(what[x],what[y]);
if(what[x]<what[x-1]) cha(what[x],what[x-1]-1,1,0);
if(what[x]<what[x+1]) cha(what[x],what[x+1]-1,1,0);
if(what[y]<what[y-1]) cha(what[y],what[y-1]-1,1,0);
if(what[y]<what[y+1]) cha(what[y],what[y+1]-1,1,0);
return Node[0].con;
}
