#include "seats.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
int h,w;
int r[1000010];
int c[1000010];
pii arr[1000010];
//segtree
pii sum[8000000];
pii minimo[8000000];
int counter[8000000];
vector<vector<int> >table;
void update_pos(int a, int b){
if(a<0 || a>h-1)return;
if(b<0 || b>w-1)return;
int t[3][3];
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)t[i][j]=1;
}//cout<<a<<" "<<b<<endl;
t[1][1]=0;
if(a==0 || b==0 || table[a-1][b-1]>table[a][b])t[0][0]=0;
if(a==0 || b==w-1 || table[a-1][b+1]>table[a][b])t[0][2]=0;
if(a==h-1 || b==0 || table[a+1][b-1]>table[a][b])t[2][0]=0;
if(a==h-1 || b==w-1 || table[a+1][b+1]>table[a][b])t[2][2]=0;
if(a==0 || table[a-1][b]>table[a][b])t[0][1]=0;
if(b==0 || table[a][b-1]>table[a][b])t[1][0]=0;
if(a==h-1 || table[a+1][b]>table[a][b])t[2][1]=0;
if(b==w-1 || table[a][b+1]>table[a][b])t[1][2]=0;
/*for(int i=0;i<3;i++){
for(int j=0;j<3;j++)cout<<t[i][j];
cout<<endl;
}cout<<endl;*/
int x,y,z,w;
x=t[0][0]+t[0][1]+t[1][0]+t[1][1];
y=t[1][0]+t[1][1]+t[2][0]+t[2][1];
z=t[0][1]+t[0][2]+t[1][1]+t[1][2];
w=t[1][1]+t[1][2]+t[2][1]+t[2][2];
int cnt[5];
for(int i=0;i<5;i++)cnt[i]=0;
cnt[x]++;
cnt[y]++;
cnt[z]++;
cnt[w]++;
//cout<<table[a][b]<<" "<<x<<endl;
//cout<<cnt[0]-cnt[1]<<endl;
arr[table[a][b]].first=cnt[0]-cnt[1];
arr[table[a][b]].second=cnt[2]-cnt[3];
}
pii Sum(pii a, pii b){
pii c=pii(a.first+b.first,a.second+b.second);
return c;
}
pii min(pii a, pii b){
if(a.second<b.second)return a;
if(a.second>b.second)return b;
if(a.first>b.first)return b;
return a;
}
void build(int a, int b, int node){
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
sum[node]=Sum(sum[2*node],sum[2*node+1]);
minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
counter[node]+=counter[2*node+1];
}
}
void update(int a, int b, int node, int pos){
if(pos<a || b<pos)return;
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,pos);
update(mid+1,b,2*node+1,pos);
sum[node]=Sum(sum[2*node],sum[2*node+1]);
minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
counter[node]+=counter[2*node+1];
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
for(int i=0;i<h;i++){
vector<int> a;
for(int j=0;j<w;j++)a.push_back(-1);
table.push_back(a);
}
for(int i=0;i<w*h;i++){
r[i]=R[i];
c[i]=C[i];
table[R[i]][C[i]]=i;
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++)update_pos(i,j);
}
build(0,w*h-1,1);
//for(int i=0;i<h*w;i++)cout<<arr[i].second<<endl;
//cout<<counter[1]<<endl;
}
int swap_seats(int a, int b) {
swap(table[r[a]][c[a]],table[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
for(int i=-1;i<2;i++){
for(int j=-1;j<2;j++){
update_pos(r[a]+i,c[a]+j);
if(r[a]+i>=0 && r[a]+i<=h-1 && c[a]+j>=0 && c[a]+j<=w-1)update(0,h*w-1,1,table[r[a]+i][c[a]+j]);
update_pos(r[b]+i,c[b]+j);
if(r[b]+i>=0 && r[b]+i<=h-1 && c[b]+j>=0 && c[b]+j<=w-1)update(0,h*w-1,1,table[r[b]+i][c[b]+j]);
}
}
//build(0,h*w-1,1);
/*int cnt=0;
int one=0;
int three=0;
for(int i=0;i<h*w;i++){
three+=arr[i].second;
one+=arr[i].first;
if(one==4 && three==0){
cnt++;
}
}*/
return counter[1];
}
