#include "seats.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pi4;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=1000010, LOG=18;
pi4 combine(pi4 a, pi4 b){ return {{min(a.first.first, b.first.first), min(a.first.second, b.first.second)}, {max(a.second.first, b.second.first), max(a.second.second, b.second.second)}};}
int n, m, k, H, W, x, y, t, ans;
int ok[MAXN];
pii A[MAXN];
pi4 seg[MAXN<<1];
void Set(int pos, pi4 x){
for (seg[pos+=MAXN]=x; pos>1; pos>>=1) seg[pos>>1]=combine(seg[pos], seg[pos^1]);
}
pi4 Get(int l, int r){
pi4 res=seg[0];
for (l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
if (l&1) res=combine(res, seg[l++]);
if (r&1) res=combine(res, seg[--r]);
}
return res;
}
int getS(pi4 x){
return (x.second.first-x.first.first+1)*(x.second.second-x.first.second+1);
}
void give_initial_chart(int _H, int _W, vi R, vi C) {
H=_H;
W=_W;
n=H*W;
fill(seg, seg+MAXN*2, pi4(pii(inf, inf), pii(-1, -1)));
for (int i=0; i<n; i++){
A[i]={R[i], C[i]};
Set(i, {A[i], A[i]});
ans+=(ok[i]=(getS(seg[1])==i+1));
}
}
int swap_seats(int a, int b){
if (a>b) swap(a, b);
swap(A[a], A[b]);
Set(a, {A[a], A[a]});
Set(b, {A[b], A[b]});
pi4 curr=Get(0, a);
for (int i=a; i<b; i++){
curr=combine(curr, pi4(A[i], A[i]));
ans-=ok[i];
ok[i]=(getS(curr)==i+1);
ans+=ok[i];
}
return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
