#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
#define lc (id<<1)
#define rc ((id<<1)|1)
#define defm int m=((l+r)>>1)
const int N=1000050;
int n,h,w,r[N],c[N];
vector<int> a[N];
struct node{
int mn,cnt,bad,lzmn,lzbad;
}seg[N<<2];
node merge(node a,node b){
int currmn=1e9,cnt=0;
if (!a.bad){
currmn=a.mn,cnt=a.cnt;
}
if (!b.bad){
if (b.mn<currmn){
currmn=b.mn,cnt=b.cnt;
}else if (b.mn==currmn){
cnt+=b.cnt;
}
}
return {currmn,cnt,min(a.bad,b.bad),0,0};
}
void pushmn(int id,int mult){
seg[id].lzmn+=mult;
seg[id].mn+=mult;
}
void pushbad(int id,int mult){
seg[id].lzbad+=mult;
seg[id].bad+=mult;
}
void build(int id,int l,int r){
if (l==r){
seg[id].cnt=1;
return;
}
defm;
build(lc,l,m);
build(rc,m+1,r);
seg[id]=merge(seg[lc],seg[rc]);
}
void modify1(int id,int l,int r,int ql,int qr,int mult){
if (qr<l||ql>r) return;
if (l>=ql&&r<=qr){
pushmn(id,mult);
return;
}
defm;
pushmn(lc,seg[id].lzmn); pushmn(rc,seg[id].lzmn);
pushbad(lc,seg[id].lzbad); pushmn(rc,seg[id].lzbad);
seg[id].lzmn=seg[id].lzbad=0;
modify1(lc,l,m,ql,qr,mult);
modify1(rc,m+1,r,ql,qr,mult);
seg[id]=merge(seg[lc],seg[rc]);
}
void modify2(int id,int l,int r,int ql,int qr,int mult){
if (qr<l||ql>r) return;
if (l>=ql&&r<=qr){
pushbad(id,mult);
return;
}
defm;
pushmn(lc,seg[id].lzmn); pushmn(rc,seg[id].lzmn);
pushbad(lc,seg[id].lzbad); pushmn(rc,seg[id].lzbad);
seg[id].lzmn=seg[id].lzbad=0;
modify2(lc,l,m,ql,qr,mult);
modify2(rc,m+1,r,ql,qr,mult);
seg[id]=merge(seg[lc],seg[rc]);
}
void check(int x,int y,int mult){
int srt[4]={a[x-1][y-1],a[x-1][y],a[x][y-1],a[x][y]};
sort(srt,srt+4);
modify1(1,0,n-1,srt[0],srt[1]-1,mult);
modify2(1,0,n-1,srt[2],srt[3]-1,mult);
}
vector<pair<int,int>> todo;
void bigcheck(int x){
todo.push_back({r[x],c[x]});
todo.push_back({r[x]+1,c[x]});
todo.push_back({r[x],c[x]+1});
todo.push_back({r[x]+1,c[x]+1});
}
void actualcheck(int mult){
sort(todo.begin(),todo.end());
todo.erase(unique(todo.begin(),todo.end()),todo.end());
for (auto i:todo){
check(i.first,i.second,mult);
}
todo.clear();
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
h=H,w=W,n=h*w;
for (int i=0;i<=h+1;i++) a[i].resize(w+2);
for (int i=0;i<n;i++) r[i]=R[i]+1,c[i]=C[i]+1;
for (int i=0;i<=h+1;i++) for (int j=0;j<=w+1;j++) a[i][j]=1e9;
for (int i=0;i<n;i++) a[r[i]][c[i]]=i;
build(1,0,n-1);
for (int i=1;i<=h+1;i++) for (int j=1;j<=w+1;j++) check(i,j,1);
//cout<<seg[1].mn<<" "<<seg[1].cnt<<" "<<seg[1].bad<<"\n";
}
int swap_seats(int x,int y){
bigcheck(x);
bigcheck(y);
actualcheck(-1);
swap(r[x],r[y]);
swap(c[x],c[y]);
a[r[x]][c[x]]=x;
a[r[y]][c[y]]=y;
bigcheck(x);
bigcheck(y);
actualcheck(1);
if (seg[1].mn==4) return seg[1].cnt;
return 0;
}
/*int main(){
int h,w,q,r,c;
vector<int> rr,cc;
cin>>h>>w>>q;
for (int i=0;i<h*w;i++){
cin>>r>>c;
rr.push_back(r);
cc.push_back(c);
}
init(h,w,rr,cc);
while (q--){
cin>>r>>c;
cout<<swapseat(r,c)<<"\n";
}
}*/
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
