#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "seats.h"
using namespace std;
const int maxn=1000005;
const int dx[4]={0,0,1,1},dy[4]={0,1,0,1};
int H,W,NUM;
int val[maxn],presum[maxn];
vector<int> R,C;
int S[maxn],T[maxn];
struct node
{
int dta;
int s,cnt;
node *lc,*rc;
void tagdta(const int &c)
{
s+=c;
dta+=c;
}
void downdate()
{
if(dta)
{
if(lc)lc->tagdta(dta);
if(rc)rc->tagdta(dta);
dta=0;
}
}
void update()
{
if(lc->s<rc->s)
{
s=lc->s;
cnt=lc->cnt;
}
else if(rc->s<lc->s)
{
s=rc->s;
cnt=rc->cnt;
}
else
{
s=lc->s;
cnt=lc->cnt+rc->cnt;
}
}
void Add(int l,int r,const int &a,const int &b,const int &c)
{
if(l>=a&&r<=b)
{
tagdta(c);
return;
}
int mid=l+r>>1;
downdate();
if(a<=mid)lc->Add(l,mid,a,b,c);
if(b>mid)rc->Add(mid+1,r,a,b,c);
update();
}
}ndl[maxn*2],*ns=ndl,*root;
node* build(int l,int r)
{
node *x=ns++;
x->dta=0;
if(l==r)
{
x->s=presum[l];
x->cnt=1;
x->lc=x->rc=NULL;
}
else
{
int mid=l+r>>1;
x->lc=build(l,mid);
x->rc=build(mid+1,r);
x->update();
}
return x;
}
int& seat(int *s,const int &x,const int &y)
{
if(x>=0&&x<H&&y>=0&&y<W)return s[x*W+y];
return NUM;
}
const int ValTable[2][3]={
{1,-1,-1},
{1,1,-1}
};
int CalcVal(int *s,const int &x,const int &y,const int w=15)
{
int res=0;
for(int k=0;k<4;k++)
if(w>>k&1)
{
int i=x-1+dx[k];
int j=y-1+dy[k];
int t=seat(s,x,y);
int a=seat(s,i+dx[k^1],j+dy[k^1]);
int b=seat(s,i+dx[k^2],j+dy[k^2]);
int c=seat(s,i+dx[k],j+dy[k]);
res+=ValTable[c<t][(a<t)+(b<t)];
}
//cout<<endl;
return res;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
::H=H;
::W=W;
NUM=H*W;
::R.assign(NUM,0);
::C.assign(NUM,0);
for(int i=0;i<NUM;i++)
{
::R[i]=R[i];
::C[i]=C[i];
seat(S,R[i],C[i])=seat(T,R[i],C[i])=i;
}
for(int i=0;i<NUM;i++)
{
val[i]=CalcVal(S,R[i],C[i]);
if(i==0)presum[i]=val[i];
else presum[i]=presum[i-1]+val[i];
}
//for(int i=0;i<NUM;i++)cout<<val[i]<<' ';cout<<endl;
root=build(0,NUM-1);
}
void UpdateVal(int x,int v)
{
root->Add(0,NUM-1,x,NUM-1,v-val[x]);
val[x]=v;
}
int swap_seats(int a, int b)
{
swap(seat(T,R[a],C[a]),seat(T,R[b],C[b]));
vector<int> p;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
{
int t;
t=seat(T,R[a]+i,C[a]+j);
if(t!=NUM)p.push_back(t);
t=seat(T,R[b]+i,C[b]+j);
if(t!=NUM)p.push_back(t);
}
swap(R[a],R[b]);
swap(C[a],C[b]);
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
for(auto x:p)
{
UpdateVal(x,CalcVal(T,R[x],C[x]));
}
swap(seat(S,R[a],C[a]),seat(S,R[b],C[b]));
if(root->s!=4)return 0;
return root->cnt;
}
