#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int Min,Minnum;
int a,b;
int tag;
node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
}
}*root;
int Min(node *n){
return n->Min+n->tag;
}
void pull(node *n){
if(Min(n->l)==Min(n->r)){
n->Min=Min(n->l);
n->Minnum=n->l->Minnum+n->r->Minnum;
}
else if(Min(n->l)>Min(n->r)){
n->Min=Min(n->r);
n->Minnum=n->r->Minnum;
}
else{
n->Min=Min(n->l);
n->Minnum=n->l->Minnum;
}
}
void push(node *n){
n->l->tag+=n->tag;
n->r->tag+=n->tag;
n->tag=0;
}
void build(node *n,int *a){
if(n->a==n->b){
n->Min=a[n->a];
return;
}
int mid=(n->a+n->b)/2;
n->l=new node(n->a,mid);
n->r=new node(mid+1,n->b);
build(n->l,a);
build(n->r,a);
pull(n);
}
void add(node *n,int l,int r,int k){
if(l>r)return;
// if(n==root){
// printf("%d %d %d\n",l,r,k);
// }
if(n->a>=l&&n->b<=r){
n->tag+=k;
return;
}
if(n->b<l||n->a>r)return;
push(n);
add(n->l,l,r,k);
add(n->r,l,r,k);
pull(n);
}
int query(node *n,int l,int r){
if(l>r)return 0;
if(n->a>=l&&n->b<=r){
// printf("%d %d %d %d %d\n",Min(n),n->a,n->b,n->tag,n->Min);
assert(Min(n)>=4);
if(Min(n)==4)return n->Minnum;
else return 0;
}
if(n->b<l||n->a>r)return 0;
push(n);
int x=query(n->l,l,r)+query(n->r,l,r);
pull(n);
return x;
}
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
#define mp make_pair
pii p[1000005];
vector<vector<int> > v;
int X[4]={0,0,1,1};
int Y[4]={0,1,0,1};
int len;
int a[1000005];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
v.resize(H+2,vector<int>(W+2,H*W));
for(int i = 0;i<H*W;i++){
//printf("%d %d %d %d\n",H,W,R[i]+1,C[i]+1);
p[i]=mp(R[i]+1,C[i]+1);
//printf("%d %d %d\n",v[R[i]+1][C[i]+1],R[i],C[i]);
// assert(v[R[i]+1][C[i]+1]==1e9);
v[R[i]+1][C[i]+1]=i;
}
len=H*W-1;
root= new node(0,H*W-1);
//build(root);
for(int i =0;i<=H;i++){
for(int j=0;j<=W;j++){
int tmp[4];
for(int k =0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
a[tmp[0]]++;
a[tmp[1]]--;
a[tmp[2]]++;
a[tmp[3]]--;
//add(root,tmp[0],tmp[1]-1,1);
//add(root,tmp[1],len,-1);
// add(root,tmp[2],tmp[3]-1,1);
// add(root,tmp[3],len,-1);
}
}
for(int i = 1;i<=H*W;i++)a[i]+=a[i-1];
build(root,a);
}
int swap_seats(int a, int b) {
// printf("%d %d\n",a,b);
for(int t=0;t<2;t++){
for(int i=p[a].x-1;i<=p[a].x;i++){
for(int j=p[a].y-1;j<=p[a].y;j++){
int tmp[4];
for(int k=0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
add(root,tmp[0],tmp[1]-1,-1);
// add(root,tmp[1],len,1);
add(root,tmp[2],tmp[3]-1,-1);
//add(root,tmp[3],len,1);
}
}
swap(a,b);
}
swap(p[a],p[b]);
v[p[a].x][p[a].y]=a;
v[p[b].x][p[b].y]=b;
for(int t=0;t<2;t++){
for(int i=p[a].x-1;i<=p[a].x;i++){
for(int j=p[a].y-1;j<=p[a].y;j++){
int tmp[4];
for(int k=0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
add(root,tmp[0],tmp[1]-1,1);
//add(root,tmp[1],len,-1);
add(root,tmp[2],tmp[3]-1,1);
//add(root,tmp[3],len,-1);
}
}
swap(a,b);
}
// printf("%d\n",query(root,0,len));
return query(root,0,len);
}
