#include "seats.h"
#include <iostream>
using namespace std;
vector<int> r;
long long int h,w,num=1,maxx,minx,maxy,miny,c,lx[1000005],rx[1000005],ly[1000005],ry[1000005],d,ans[1000005],x[1000005],y[1000005],n,maxxtree[4000005],minxtree[4000005],maxytree[4000005],minytree[4000005];
int build(int s,int e,int t)
{
if(s==e)
{
maxxtree[t]=x[e];
minxtree[t]=x[e];
maxytree[t]=y[e];
minytree[t]=y[e];
return 0;
}
else
{
build(s,(s+e)/2,t*2);
build((s+e)/2+1,e,t*2+1);
maxxtree[t]=max(maxxtree[t*2],maxxtree[t*2+1]);
minxtree[t]=min(minxtree[t*2],minxtree[t*2+1]);
maxytree[t]=max(maxytree[t*2],maxytree[t*2+1]);
minytree[t]=min(minytree[t*2],minytree[t*2+1]);
//cout<<s<<" "<<e<<" "<<t<<" "<<minxtree[t]<<" "<<maxxtree[t]<<" "<<minytree[t]<<" "<<maxytree[t]<<endl;
return 0;
}
}
int change(int s,int e,int t)
{
if(c<s || c>e)return 0;
if(s==e)
{
maxxtree[t]=x[e];
minxtree[t]=x[e];
maxytree[t]=y[e];
minytree[t]=y[e];
return 0;
}
change(s,(s+e)/2,t*2);
change((s+e)/2+1,e,t*2+1);
maxxtree[t]=max(maxxtree[t*2],maxxtree[t*2+1]);
minxtree[t]=min(minxtree[t*2],minxtree[t*2+1]);
maxytree[t]=max(maxytree[t*2],maxytree[t*2+1]);
minytree[t]=min(minytree[t*2],minytree[t*2+1]);
}
int find(int s,int e,int t)
{
//cout<<s<<" "<<e<<" "<<t<<" "<<endl;
if(c>e || d<s)return 0;
else if(c<=s && e<=d)
{
//cout<<s<<" "<<e<<" "<<t<<endl;
minx=min(minxtree[t],minx);
maxx=max(maxxtree[t],maxx);
miny=min(minytree[t],miny);
maxy=max(maxytree[t],maxy);
//cout<<minxtree[t]<<" "<<maxxtree[t]<<" "<<minytree[t]<<" "<<maxytree[t]<<endl;
}
else
{
find(s,(s+e)/2,t*2);
find((s+e)/2+1,e,t*2+1);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=H*W;
h=H,w=W;
if(H<=1000 && W<=1000)
{
{
for(int i=0;i<n;i++)
{
x[i]=R[i];
y[i]=C[i];
}
build(0,n-1,1);
}
}
else
{
for(int i=0;i<n;i++)
{
x[i]=R[i];
y[i]=C[i];
}
ans[0]=1,lx[0]=x[0],rx[0]=x[0],ly[0]=y[0],ry[0]=y[0];
for(int i=1;i<n;i++)
{
lx[i]=min(x[i],lx[i-1]);
rx[i]=max(x[i],rx[i-1]);
ly[i]=min(y[i],ly[i-1]);
ry[i]=max(y[i],ry[i-1]);
//cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
if((rx[i]-lx[i]+1)*(ry[i]-ly[i]+1)==i+1)
{
ans[i]=1;
num++;
}
}
}
}
int swap_seats(int a, int b) {
swap(x[a],x[b]);
swap(y[a],y[b]);
//for(int i=0;i<n;i++)cout<<x[i]<<" "<<y[i]<<" ";
//cout<<endl;
if(a>b)swap(a,b);
if(h<=1000 && w<=1000)
{
c=a;
change(0,n-1,1);
c=b;
change(0,n-1,1);
int ans=1;
maxx=x[0],minx=x[0],maxy=y[0],miny=y[0];
for(int i=1;i<n;i++)
{
minx=min(x[i],minx);
maxx=max(x[i],maxx);
miny=min(y[i],miny);
maxy=max(y[i],maxy);
//cout<<i<<" "<<x[i]<<" "<<y[i]<<" "<<minx<<" "<<maxx<<" "<<miny<<" "<<maxy<<endl;
//system("pause");
if((maxx-minx+1)*(maxy-miny+1)==i+1)ans++;
else
{
c=i,d=(maxx-minx+1)*(maxy-miny+1)-1;
//cout<<c<<" "<<d<<" "<<i<<endl;
i=(maxx-minx+1)*(maxy-miny+1)-2;
find(0,n-1,1);
//cout<<i<<endl;
}
}
return ans;
}
else
{
if(a==0)a=1;
ans[0]=1,lx[0]=x[0],rx[0]=x[0],ly[0]=y[0],ry[0]=y[0];
for(int i=a;i<=b;i++)
{
lx[i]=min(x[i],lx[i-1]);
rx[i]=max(x[i],rx[i-1]);
ly[i]=min(y[i],ly[i-1]);
ry[i]=max(y[i],ry[i-1]);
//cout<<num<<" "<<ans[i]<<" "<<i<<" "<<lx[i]<<" "<<rx[i]<<" "<<ly[i]<<" "<<ry[i]<<endl;
if((rx[i]-lx[i]+1)*(ry[i]-ly[i]+1)==i+1)
{
if(ans[i]==0)
{
num++;
ans[i]=1;
}
}
else if(ans[i]==1)
{
num--;
ans[i]=0;
}
//cout<<num<<endl;
}
//system("pause");
return num;
}
}
