#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
const int MAXN=1e6+10;
typedef tuple<int,int,int> trio;
typedef pair<int,int> pii;
struct node{
int mx,mn,px,pm;
node operator+(const node& nd){
node c;
c.mx=max(this->mx,nd.mx);
c.mn=min(this->mn,nd.mn);
c.px=this->px;
c.pm=this->pm;
return c;
}
};
int ans,n;
vector<pii> v;
node seg[4*MAXN],seg1[MAXN];
void build(int ind,int l,int r){
if(l==r){
seg[ind].mx=seg[ind].mn=seg[ind].px=seg[ind].pm=v[l].F;
seg1[ind].mx=seg1[ind].px=seg1[ind].pm=seg1[ind].mn=v[l].S;
return;
}
int m=(l+r)>>1; build(2*ind,l,m); build(2*ind+1,m+1,r);
seg[ind]=seg[2*ind]+seg[2*ind+1];
seg1[ind]=seg1[2*ind]+seg1[2*ind+1];
}
void update(int ind,int l,int r,int a){
if(l==r){
seg[ind].mx=seg[ind].mn=v[l].F;
seg1[ind].mx=seg1[ind].mn=v[l].S;
seg[ind].mx=seg[ind].mn=seg[ind].px=seg[ind].pm=v[l].F;
seg1[ind].mx=seg1[ind].px=seg1[ind].pm=seg1[ind].mn=v[l].S;
return;
}
int m=(l+r)>>1;
if(a<=m) update(2*ind,l,m,a);
else update(2*ind+1,m+1,r,a);
seg[ind]=seg[2*ind]+seg[2*ind+1];
seg1[ind]=seg1[2*ind]+seg1[2*ind+1];
}
int walk(int ind,int l,int r,int val){ //tem o mx<=val
if(l==r) return l;
int m=(l+r)>>1;
if(seg[2*ind].mx<=val && seg[2*ind+1].pm<=val) return walk(2*ind+1,m+1,r,val);
return walk(2*ind,l,m,val);
}
int w1(int ind,int l,int r,int val){ //tem o mn>=val
if(l==r) return l;
int m=(l+r)>>1;
if(seg[2*ind].mn>=val && seg[2*ind+1].pm>=val) return w1(2*ind+1,m+1,r,val);
return w1(2*ind,l,m,val);
}
int walk1(int ind,int l,int r,int val){ //tem o mx<=val
if(l==r) return l;
int m=(l+r)>>1;
if(seg1[2*ind].mx<=val && seg1[2*ind+1].pm<=val) return walk1(2*ind+1,m+1,r,val);
return walk1(2*ind,l,m,val);
}
int w2(int ind,int l,int r,int val){ //tem o mn>=val
if(l==r) return l;
int m=(l+r)>>1;
if(seg1[2*ind].mn>=val && seg1[2*ind+1].pm>=val) return w2(2*ind+1,m+1,r,val);
return w2(2*ind,l,m,val);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
v.resize(W*H);
fall(i,0,W*H-1) v[i]={R[i],C[i]};
build(1,0,W*H-1);
n=H*W;
return;
}
int swap_seats(int a, int b){
swap(v[a],v[b]);
update(1,0,n-1,a); update(1,0,n-1,b);
vector<pii> line;
int l=0;
fall(i,v[0].F,seg[1].mx){
int id=walk(1,0,n-1,i);
line.pb({l,0});
l=id+1;
}
l=0;
rfall(i,v[0].F,0){
int id=w1(1,0,n-1,i);
line.pb({l,0});
l=id+1;
}
l=0;
fall(i,v[0].S,seg1[1].mx){
int id=walk1(1,0,n-1,i);
line.pb({l,1});
l=id+1;
}
l=0;
rfall(i,v[0].S,0){
int id=w2(1,0,n-1,i);
line.pb({l,1});
l=id+1;
}
sort(all(line));
int ca=-1,cb=-1;
int ans=0;
fall(i,0,sz(line)-1){
auto [x,t]=line[i];
if(!t) ca++;
else cb++;
int last=n;
if(i!=sz(line)-1){
last=line[i+1].F;
}
if(ca*cb>x && ca*cb<=last) ans++;
}
return ans;
}
