#include "seats.h"
#include <stdio.h>
using namespace std;
int N,H,W;
pair < int , int > all[1000005];
vector < vector < int > > what;
vector < int > tt;
int how1[1000005]={0};
int how2[1000005]={0};
struct A
{
int l,r;
int nxl,nxr;
int small1,small2,con;
int add1,add2;
}Node[2000005];
int now=1;
void UPD(int here)
{
Node[Node[here].nxl].add1+=Node[here].add1;
Node[Node[here].nxl].small1+=Node[here].add1;
Node[Node[here].nxr].add1+=Node[here].add1;
Node[Node[here].nxr].small1+=Node[here].add1;
Node[here].add1=0;
Node[Node[here].nxl].add2+=Node[here].add2;
Node[Node[here].nxl].small2+=Node[here].add2;
Node[Node[here].nxr].add2+=Node[here].add2;
Node[Node[here].nxr].small2+=Node[here].add2;
Node[here].add2=0;
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].small1=0;
Node[here].small2=0;
Node[here].add1=0;
Node[here].add2=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 cha1(int l,int r,int con,int here)
{
if(l>r) return;
//if(here==0) for(int i=l;i<=r;i++) how1[i]+=con;
if(l==Node[here].l&&r==Node[here].r)
{
Node[here].add1+=con;
Node[here].small1+=con;
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxr);
else
{
cha1(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha1((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
}
Node[here].con=0;
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxl].con;
if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxr].con;
//printf("%d %d %d %d\n",Node[here].l,Node[here].r,Node[here].small1,Node[here].con);
}
void cha2(int l,int r,int con,int here)
{
if(l>r) return;
//if(here==0) for(int i=l;i<=r;i++) how2[i]+=con;
if(l==Node[here].l&&r==Node[here].r)
{
Node[here].add2+=con;
Node[here].small2+=con;
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxr);
else
{
cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
}
Node[here].con=0;
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxl].con;
if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxr].con;
}
void F(int x,int y,int t)
{
int a=what[x][y],b=what[x+1][y],c=what[x][y+1],d=what[x+1][y+1];
if(a>b) swap(a,b);
if(a>c) swap(a,c);
if(a>d) swap(a,d);
if(b>c) swap(b,c);
if(b>d) swap(b,d);
if(c>d) swap(c,d);
cha1(a,b-1,t,0);
cha2(c,d-1,t,0);
/*for(int i=0;i<N;i++) printf("%d ",how1[i]);
printf("\n");
for(int i=0;i<N;i++) printf("%d ",how2[i]);
printf("\n");*/
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
int i,j;
N=H*W;
::H=H;
::W=W;
for(j=0;j<=W+1;j++) tt.push_back(N);
for(i=0;i<=H+1;i++) what.push_back(tt);
for(i=0;i<N;i++)
{
R[i]++;
C[i]++;
all[i]=make_pair(R[i],C[i]);
what[R[i]][C[i]]=i;
}
build(0,N-1,0);
for(i=0;i<=H;i++) for(j=0;j<=W;j++) F(i,j,1);
}
int swap_seats(int a, int b)
{
int x1,y1,x2,y2,ans=0;
x1=all[a].first;
y1=all[a].second;
x2=all[b].first;
y2=all[b].second;
F(x1-1,y1-1,-1);
F(x1-1,y1,-1);
F(x1,y1-1,-1);
F(x1,y1,-1);
F(x2-1,y2-1,-1);
F(x2-1,y2,-1);
F(x2,y2-1,-1);
F(x2,y2,-1);
swap(all[a],all[b]);
swap(what[x1][y1],what[x2][y2]);
F(x1-1,y1-1,1);
F(x1-1,y1,1);
F(x1,y1-1,1);
F(x1,y1,1);
F(x2-1,y2-1,1);
F(x2-1,y2,1);
F(x2,y2-1,1);
F(x2,y2,1);
/*for(int i=1;i<=H;i++)
{
for(int j=1;j<=W;j++) printf("%d ",what[i][j]);
printf("\n");
}*/
return Node[0].con;
}
