#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
int H, W, R[MAXN+10], C[MAXN+10];
vector<vector<int>> A;
int psum1[MAXN+10], psum2[MAXN+10];
pii val[4*MAXN+10], lazy[4*MAXN+10];
int cnt[4*MAXN+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
val[node]={psum1[tl], psum2[tl]};
cnt[node]=1;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}
void busy(int node, int tl, int tr)
{
if(lazy[node]==pii(0, 0)) return;
val[node].first+=lazy[node].first;
val[node].second+=lazy[node].second;
if(tl!=tr)
{
lazy[node*2].first+=lazy[node].first; lazy[node*2].second+=lazy[node].second;
lazy[node*2+1].first+=lazy[node].first; lazy[node*2+1].second+=lazy[node].second;
}
lazy[node]=pii(0, 0);
}
void update(int node, int tl, int tr, int l, int r, int v, int t)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
if(t==1) lazy[node].first+=v;
else lazy[node].second+=v;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, v, t);
update(node*2+1, mid+1, tr, l, r, v, t);
if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}
int query()
{
busy(1, 1, H*W);
if(val[1]==pii(4, 0)) return cnt[1];
else return 0;
}
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C)
{
int i, j;
H=_H; W=_W; A=vector<vector<int>>(H+2, vector<int>(W+2, H*W+1));
for(i=0; i<H*W; i++) R[i+1]=_R[i]+1, C[i+1]=_C[i]+1;
for(i=1; i<=H*W; i++) A[R[i]][C[i]]=i;
for(i=0; i<=H; i++) for(j=0; j<=W; j++)
{
vector<int> V;
V.push_back(A[i][j]);
V.push_back(A[i+1][j]);
V.push_back(A[i][j+1]);
V.push_back(A[i+1][j+1]);
sort(V.begin(), V.end());
psum1[V[0]]++; psum1[V[1]]--;
psum2[V[2]]++; psum2[V[3]]--;
}
for(i=1; i<=H*W; i++) psum1[i]+=psum1[i-1], psum2[i]+=psum2[i-1];
init(1, 1, H*W);
}
void update(int y, int x, int val)
{
vector<int> V;
V.push_back(A[y][x]);
V.push_back(A[y+1][x]);
V.push_back(A[y][x+1]);
V.push_back(A[y+1][x+1]);
sort(V.begin(), V.end());
update(1, 1, H*W, V[0], V[1]-1, val, 1);
update(1, 1, H*W, V[2], V[3]-1, val, 2);
}
int swap_seats(int a, int b)
{
int i, j;
a++; b++;
update(R[a]-1, C[a]-1, -1);
update(R[a], C[a]-1, -1);
update(R[a]-1, C[a], -1);
update(R[a], C[a], -1);
update(R[b]-1, C[b]-1, -1);
update(R[b], C[b]-1, -1);
update(R[b]-1, C[b], -1);
update(R[b], C[b], -1);
swap(R[a], R[b]); swap(C[a], C[b]); swap(A[R[a]][C[a]], A[R[b]][C[b]]);
update(R[a]-1, C[a]-1, 1);
update(R[a], C[a]-1, 1);
update(R[a]-1, C[a], 1);
update(R[a], C[a], 1);
update(R[b]-1, C[b]-1, 1);
update(R[b], C[b]-1, 1);
update(R[b]-1, C[b], 1);
update(R[b], C[b], 1);
return query();
}
