#pragma GCC optimize("O3")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ii pair<int,int>
#define INF (int)(1e9)
int n,h,w,A[1000002];
pair<ii,ii> tab[1000002],st[4000005];
vector<int> RR,c;
int ones=0,zeros=0;
void build(int node,int l,int r){
if(l==r){
st[node].fi=ii(RR[l],RR[l]);
st[node].se=ii(c[l],c[l]);
return ;
}
int med=(l+r)>>1;
build((node<<1),l,med),build((node<<1)+1,med+1,r);
st[node].fi.fi=max(st[(node<<1)].fi.fi,st[(node<<1)+1].fi.fi);
st[node].fi.se=min(st[(node<<1)].fi.se,st[(node<<1)+1].fi.se);
st[node].se.fi=max(st[(node<<1)].se.fi,st[(node<<1)+1].se.fi);
st[node].se.se=min(st[(node<<1)].se.se,st[(node<<1)+1].se.se);
}
pair<ii,ii> query(int node,int l,int r,int i,int j){
if(l>j||r<i)
return {ii(0,INF),ii(0,INF)};
if(l>=i&&r<=j)
return {st[node].fi,st[node].se};
int med=(l+r)>>1;
pair<ii,ii> L=query((node<<1),l,med,i,j),R=query((node<<1)+1,med+1,r,i,j);
L.fi.fi = max(L.fi.fi, R.fi.fi);
L.fi.se = min(L.fi.se, R.fi.se);
L.se.fi = max(L.se.fi, R.se.fi);
L.se.se = min(L.se.se, R.se.se);
return L;
}
void update(int node,int l,int r,int idx,int x,int y){
if(l==r){
st[node].fi=ii(x,x);
st[node].se=ii(y,y);
return ;
}
int med=(l+r)>>1;
if(idx<=med) update((node<<1),l,med,idx,x,y);
else update((node<<1)+1,med+1,r,idx,x,y);
st[node].fi.fi=max(st[(node<<1)].fi.fi,st[(node<<1)+1].fi.fi);
st[node].fi.se=min(st[(node<<1)].fi.se,st[(node<<1)+1].fi.se);
st[node].se.fi=max(st[(node<<1)].se.fi,st[(node<<1)+1].se.fi);
st[node].se.se=min(st[(node<<1)].se.se,st[(node<<1)+1].se.se);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n=H*W,h=H,w=W;
RR=R,c=C;
if(H<=1000&&W<=1000){
build(1,0,n-1);
return;
}
else{
for (int i = 0; i < n; ++i)
{
tab[i].fi=ii(R[i],C[i]);
tab[i].se=ii(R[i],C[i]);
if(i){
tab[i].fi.fi=max(tab[i].fi.fi,tab[i-1].fi.fi);
tab[i].fi.se=max(tab[i].fi.se,tab[i-1].fi.se);
tab[i].se.fi=min(tab[i].se.fi,tab[i-1].se.fi);
tab[i].se.se=min(tab[i].se.se,tab[i-1].se.se);
}
if((tab[i].fi.fi-tab[i].se.fi+1)*(tab[i].fi.se-tab[i].se.se+1)==(i+1))A[i]=1,ones++;
else A[i]=0,zeros++;
}
}
}
int swap_seats(int a, int b) {
if(h<=1000&&w<=1000){
if(a > b)
swap(a, b);
swap(RR[a],RR[b]),swap(c[a],c[b]);
update(1,0,n-1,a,RR[a],c[a]),update(1,0,n-1,b,RR[b],c[b]);
int ans=0;
ii X=ii(0,INF),Y=ii(0,INF);
for (int i = 0; i < n;)
{
pair<ii,ii> q=query(1,0,n-1,0,i);
ii q1=q.fi,q2=q.se;
X.fi=max(X.fi,q1.fi),X.se=min(X.se,q1.se),Y.fi=max(Y.fi,q2.fi),Y.se=min(Y.se,q2.se);
if((X.fi-X.se+1)*(Y.fi-Y.se+1)==(i+1))
ans++,i++;
else
i=(X.fi-X.se+1)*(Y.fi-Y.se+1)-1;
}
return ans;
}
else{
swap(RR[a],RR[b]),swap(c[a],c[b]);
for (int i = min(a,b); i <= max(a,b); ++i)
{
tab[i].fi=ii(RR[i],c[i]);
tab[i].se=ii(RR[i],c[i]);
if(i){
tab[i].fi.fi=max(tab[i].fi.fi,tab[i-1].fi.fi);
tab[i].fi.se=max(tab[i].fi.se,tab[i-1].fi.se);
tab[i].se.fi=min(tab[i].se.fi,tab[i-1].se.fi);
tab[i].se.se=min(tab[i].se.se,tab[i-1].se.se);
}
if((tab[i].fi.fi-tab[i].se.fi+1)*(tab[i].fi.se-tab[i].se.se+1)==(i+1)){
if(!A[i])
A[i]=1,ones++,zeros--;
}
else {
if(A[i])
A[i]=0,ones--,zeros++;
}
}
return ones;
}
}
