#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
int h, w;
int lazy[4000005];
int segm[2][4000005];
void push_lazy(int v, int le, int ri)
{
segm[0][v]+=lazy[v];
if(le!=ri)
{
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
}
lazy[v]=0;
}
void update(int v, int le, int ri, int be, int en, int st)
{
if(segm[1][v]==0) segm[1][v]=ri-le+1;
push_lazy(v, le, ri);
//if(v==1) cout<<be<<" "<<en<<" "<<st<<endl;
if(le>en || ri<be) return;
if(be<=le && ri<=en)
{
segm[0][v]+=st;
if(le!=ri) {lazy[2*v]+=st; lazy[2*v+1]+=st;}
return;
}
int mid=(le+ri)/2;
update(2*v, le, mid, be, en, st);
update(2*v+1, mid+1, ri, be, en, st);
if(segm[0][2*v]<segm[0][2*v+1])
{
segm[0][v]=segm[0][2*v];
segm[1][v]=segm[1][2*v];
}
else if(segm[0][2*v]>segm[0][2*v+1])
{
segm[0][v]=segm[0][2*v+1];
segm[1][v]=segm[1][2*v+1];
}
else
{
segm[0][v]=segm[0][2*v+1];
segm[1][v]=segm[1][2*v]+segm[1][2*v+1];
}
}
int query(int v, int le, int ri, int be, int en, int val)
{
push_lazy(v, le, ri);
if(le>en || ri<be) return 0;
if(be<=le && ri<=en)
{
if(segm[0][v]==val) return segm[1][v];
return 0;
}
int mid=(le+ri)/2;
return query(2*v, le, mid, be, en, val) + query(2*v+1, mid+1, ri, be, en, val);
}
vector<vector<int> > tabl;
std::vector<int> rows, cols;
void upd_rect(int r, int c, int st)
{
int val[4];
val[0]=tabl[r][c];
val[1]=tabl[r+1][c];
val[2]=tabl[r][c+1];
val[3]=tabl[r+1][c+1];
sort(val, val+4);
if(val[1]==10000000) update(1, 0, h*w-1, val[0], h*w-1, st);
else update(1, 0, h*w-1, val[0], val[1]-1, st);
if(val[3]!=10000000) update(1, 0, h*w-1, val[2], val[3]-1, st);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
h=H;
w=W;
rows=R;
cols=C;
tabl.resize(H+2);
for(int i=0; i<H+2; i++)
{
tabl[i].resize(W+2);
for(int j=0; j<W+2; j++) tabl[i][j]=1e7;
}
for(int i=0; i<H*W; i++) tabl[R[i]+1][C[i]+1]=i;
for(int r=0; r<=H; r++)
{
for(int c=0; c<=W; c++)
{
upd_rect(r, c, 1);
}
}
//for(int j=1; j<=13; j++) //cout<<segm[0][j]<<" "<<segm[1][j]<<endl;
}
int swap_seats(int a, int b)
{
int r1=rows[a], r2=rows[b], c1=cols[a], c2=cols[b];
r1++;
r2++;
c1++;
c2++;
upd_rect(r1-1, c1-1, -1);
upd_rect(r1, c1-1, -1);
upd_rect(r1-1, c1, -1);
upd_rect(r1, c1, -1);
upd_rect(r2-1, c2-1, -1);
upd_rect(r2, c2-1, -1);
upd_rect(r2-1, c2, -1);
upd_rect(r2, c2, -1);
tabl[r1][c1]=b;
tabl[r2][c2]=a;
swap(rows[a], rows[b]);
swap(cols[a], cols[b]);
upd_rect(r1-1, c1-1, 1);
upd_rect(r1, c1-1, 1);
upd_rect(r1-1, c1, 1);
upd_rect(r1, c1, 1);
upd_rect(r2-1, c2-1, 1);
upd_rect(r2, c2-1, 1);
upd_rect(r2-1, c2, 1);
upd_rect(r2, c2, 1);
return query(1, 0, h*w-1, 0, h*w-1, 4);
}
