#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define pipi pair<pii,pii>
//direction of my comparator signs :(
//forgot to +1 to i-j to get size of range [i...j]
vector<pipi>sg;
vector<pii>foreach;
int n;
pipi query(int s, int e, int cn, int reqs, int reqe)
{
if(reqs==s&&reqe==e)
{
return sg[cn];
}
int m=(s+e)/2;
pipi t1={{INT_MAX,INT_MIN},{INT_MAX,INT_MIN}};
pipi t2=t1;
if(reqs<=m)
{
t1=query(s,m,cn<<1,reqs,min(m,reqe));
}
if(reqe>m)
{
t2=query(m+1,e,(cn<<1)|1,max(m+1,reqs),reqe);
}
pipi t3;
t3.ff=mp(min(t1.ff.ff,t2.ff.ff),max(t1.ff.ss,t2.ff.ss));
t3.ss=mp(min(t1.ss.ff,t2.ss.ff),max(t1.ss.ss,t2.ss.ss));
return t3;
}
void init(int s, int e, int cn)
{
if(s==e)
{
sg[cn]=mp(mp(foreach[s].ff,foreach[s].ff),mp(foreach[s].ss,foreach[s].ss));
return;
}
int m=(s+e)/2;
init(s,m,cn<<1);
init(m+1,e,(cn<<1)|1);
pipi t1=sg[cn<<1],t2=sg[(cn<<1)|1];
sg[cn].ff=mp(min(t1.ff.ff,t2.ff.ff),max(t1.ff.ss,t2.ff.ss));
sg[cn].ss=mp(min(t1.ss.ff,t2.ss.ff),max(t1.ss.ss,t2.ss.ss));
}
void update(int s, int e, int cn, int pos)
{
if(s==pos&&e==pos)
{
sg[cn]=mp(mp(foreach[s].ff,foreach[s].ff),mp(foreach[s].ss,foreach[s].ss));
return;
}
int m=(s+e)/2;
if(pos<=m)
{
update(s,m,cn<<1,pos);
}
else
{
update(m+1,e,(cn<<1)|1,pos);
}
pipi t1=sg[cn<<1],t2=sg[(cn<<1)|1];
sg[cn].ff=mp(min(t1.ff.ff,t2.ff.ff),max(t1.ff.ss,t2.ff.ss));
sg[cn].ss=mp(min(t1.ss.ff,t2.ss.ff),max(t1.ss.ss,t2.ss.ss));
}
int ans=0;
vector<bool>keyi;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
int h=H,w=W;n=h*w;
sg.resize(4*n+10);
keyi.resize(n);
for(int i=0;i<n;i++)
{
foreach.pb(mp(R[i],C[i]));
}
init(0,n-1,1);
for(int a=0;a<n;a++)
{
pipi x=query(0,n-1,1,0,a);
if((x.ff.ss-x.ff.ff+1)*(x.ss.ss-x.ss.ff+1) == a+1)
{
ans++;
keyi[a]=true;
}
else keyi[a]=false;
}
}
int swap_seats(int a, int b)
{
if(a>b)swap(a,b);
swap(foreach[a],foreach[b]);
update(0,n-1,1,a);
update(0,n-1,1,b);
for(int i=a;i<b;i++)
{
pipi x=query(0,n-1,1,0,i);
//debu(i);debu2(x.ff.ff,x.ff.ss);debu2(x.ss.ff,x.ss.ss);
//debu2((x.ff.ss-x.ff.ff)*(x.ss.ss-x.ss.ff),i+1);
if((x.ff.ss-x.ff.ff+1)*(x.ss.ss-x.ss.ff+1)==i+1)
{
//c1;
if(!keyi[i])ans++;
keyi[i]=true;
}
else
{
if(keyi[i])ans--;
keyi[i]=false;
}
}
return ans;
}
