#include<bits/stdc++.h>
#include "seats.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int P=11e5;
int ans=0;
pair<int,int> tab[N+10];
int w[N+10][4];
struct T
{
int a,b,c,d;
T operator+(const T &oth)
{
return {min(a,oth.a),max(b,oth.b),min(c,oth.c),max(d,oth.d)};
}
bool operator==(const T &oth)
{
return (a==oth.a && b==oth.b && c==oth.c && d==oth.d);
}
bool operator!=(const T &oth)
{
return (a!=oth.a || b!=oth.b || c!=oth.c || d!=oth.d);
}
};
bool hw=false;
int h,wi;
int pot;
T tree[2*P+10];
void upd_t(int x,pair<int,int> c)
{
x+=pot-1;
tree[x]={c.fi,c.fi,c.se,c.se};
for(x/=2;x>0;x/=2)
tree[x]=tree[2*x]+tree[2*x+1];
return;
}
T read_t(int r)
{
int l=pot;
r+=pot-1;
T ww={h,0,wi,0};
for(;l<=r;l/=2,r/=2)
{
if(l%2==1)
ww=ww+tree[l++];
if(r%2==0)
ww=ww+tree[r--];
}
return ww;
}
int bs_t(int x,T d)
{
x+=pot-1;
while(d+tree[x]==d)
{
if(x%2==0)
x/=2;
else
{
x++;
x/=2;
}
}
while(x<pot)
{
if(d+tree[2*x]!=d)
x=2*x;
else
x=2*x+1;
}
return x-pot+1;
}
void solvehw(int H,int W,vector<int> R,vector<int> C)
{
h=H;
wi=W;
for(pot=1;pot<h*wi;pot*=2);
for(int i=1;i<=h*wi;i++)
tree[pot+i-1]={R[i-1],R[i-1],C[i-1],C[i-1]};
for(int i=pot-1;i>0;i--)
tree[i]=tree[2*i]+tree[2*i+1];
return;
}
int swaphw(int a,int b)
{
upd_t(a,tab[b]);
upd_t(b,tab[a]);
swap(tab[a],tab[b]);
int ww=1;
int lst=1;
T d={tab[1].fi,tab[1].fi,tab[1].se,tab[1].se};
while(d.b-d.a+1<h || d.d-d.c+1<wi)
{
int bg=bs_t(lst,d);
int tmp=(d.b-d.a+1)*(d.d-d.c+1);
if(lst<=tmp && tmp<bg)
ww++;
lst=bg;
d=read_t(lst);
}
return ww;
}
bool is_ok(int x)
{
return x==(w[x][1]-w[x][0]+1)*(w[x][3]-w[x][2]+1);
}
void upd(int x)
{
w[x][0]=min(w[x-1][0],tab[x].fi);
w[x][1]=max(w[x-1][1],tab[x].fi);
w[x][2]=min(w[x-1][2],tab[x].se);
w[x][3]=max(w[x-1][3],tab[x].se);
return;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
int n=H*W;
for(int i=1;i<=n;i++)
tab[i]={R[i-1],C[i-1]};
if(H<=1000 && W<=1000)
{
hw=true;
solvehw(H,W,R,C);
return;
}
w[0][0]=H;
w[0][1]=0;
w[0][2]=W;
w[0][3]=0;
for(int i=1;i<=n;i++)
{
upd(i);
ans+=is_ok(i);
}
return;
}
int swap_seats(int a,int b)
{
a++;
b++;
if(a>b)
swap(a,b);
if(hw)
return swaphw(a,b);
swap(tab[a],tab[b]);
for(int i=a;i<b;i++)
{
ans-=is_ok(i);
upd(i);
ans+=is_ok(i);
}
return ans;
}
