#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
int n;
int h, w;
int pos[1000005][2];
int mi_tree[4000005][2];
int ma_tree[4000005][2];
void update(int v, int le, int ri, int id)
{
if(ri<id || le>id) return;
if(le==ri)
{
mi_tree[v][0]=pos[le][0];
mi_tree[v][1]=pos[le][1];
ma_tree[v][0]=pos[le][0];
ma_tree[v][1]=pos[le][1];
}
else
{
int mid=(le+ri)/2;
update(2*v, le, mid, id);
update(2*v+1, mid+1, ri, id);
mi_tree[v][0]=min(mi_tree[2*v][0], mi_tree[2*v+1][0]);
mi_tree[v][1]=min(mi_tree[2*v][1], mi_tree[2*v+1][1]);
ma_tree[v][0]=max(ma_tree[2*v][0], ma_tree[2*v+1][0]);
ma_tree[v][1]=max(ma_tree[2*v][1], ma_tree[2*v+1][1]);
}
}
pair<pair<int, int>, pair<int, int> > query(int v, int le, int ri, int be, int en)
{
if(le>en || ri<be) return {{1e9, 0}, {1e9, 0}};
if(be<=le && ri<=en) return {{mi_tree[v][0], ma_tree[v][0]}, {mi_tree[v][1], ma_tree[v][1]}};
else
{
int mid=(le+ri)/2;
pair<pair<int, int>, pair<int, int> > pr1=query(2*v, le, mid, be, en), pr2=query(2*v+1, mid+1, ri, be, en);
return {{min(pr1.first.first, pr2.first.first), max(pr1.first.second, pr2.first.second)}, {min(pr1.second.first, pr2.second.first), max(pr1.second.second, pr2.second.second)}};
}
}
int br=0;
int ans[1000005];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
h=H;
w=W;
n=h*w;
for(int i=0; i<n; i++) pos[i][0]=R[i], pos[i][1]=C[i];
for(int i=0; i<n; i++) update(1, 0, n-1, i);
for(int i=0; i<n; i++)
{
pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
if(t==i+1) {ans[i]=1; br++;}
}
}
int swap_seats(int a, int b)
{
if(a>b) swap(a, b);
swap(pos[a][0], pos[b][0]);
swap(pos[a][1], pos[b][1]);
update(1, 0, n-1, a);
update(1, 0, n-1, b);
for(int i=a; i<b; i++)
{
br-=ans[i];
ans[i]=0;
pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
if(t==i+1) {ans[i]=1; br++;}
}
return br;
}
