#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, int DEF>
class Seg {
public:
vi SEG;
int sz;
T t;
void resize(int _sz) {
sz = _sz;
SEG.resize(sz*4);
}
void build(vi& f, int p=0, int l=0, int r=-1) {
if(r == -1) r = sz;
if(l == r) {
SEG[p] = f[l];
return;
}
int m=(l+r)/2;
build(f,p*2+1,l,m);
build(f,p*2+2,m+1,r);
if(t(SEG[p*2+1], SEG[p*2+2])) SEG[p] = SEG[p*2+1];
else SEG[p] = SEG[p*2+2];
}
int get(int i, int j, int p=0, int l=0, int r=-1) {
if(r == -1) r = sz;
if(j < l || i > r) return DEF;
if(i <= l && j >= r) return SEG[p];
int m=(l+r)/2;
int a=get(i,j,p*2+1,l,m);
int b=get(i,j,p*2+2,m+1,r);
if(t(a,b)) return a;
else return b;
}
void set(int i, int x, int p=0, int l=0, int r=-1) {
if(r == -1) r = sz;
if(i < l || i > r) return;
if(l == r) {
SEG[p] = x;
return;
}
int m=(l+r)/2;
set(i,x,p*2+1,l,m);
set(i,x,p*2+2,m+1,r);
if(t(SEG[p*2+1], SEG[p*2+2])) SEG[p] = SEG[p*2+1];
else SEG[p] = SEG[p*2+2];
}
};
int h, w, n;
vi r, c;
vii pos;
Seg<less<int>, 10000000> SEGMINR, SEGMINC;
Seg<greater<int>, -10000000> SEGMAXR, SEGMAXC;
void give_initial_chart(int H, int W, vi R, vi C) {
h=H, w=W, r=R, c=C;
n = h*w;
pos.resize(n);
RE(i,n) pos[i] = {r[i], c[i]};
SEGMINR.resize(n);
SEGMAXR.resize(n);
SEGMINC.resize(n);
SEGMAXC.resize(n);
SEGMINR.build(r);
SEGMAXR.build(r);
SEGMINC.build(c);
SEGMAXC.build(c);
}
int swap_seats(int a, int b) {
if(b < a) swap(a,b);
swap(pos[a], pos[b]);
SEGMINR.set(a, pos[a].fi);
SEGMAXR.set(a, pos[a].fi);
SEGMINC.set(a, pos[a].se);
SEGMAXC.set(a, pos[a].se);
SEGMINR.set(b, pos[b].fi);
SEGMAXR.set(b, pos[b].fi);
SEGMINC.set(b, pos[b].se);
SEGMAXC.set(b, pos[b].se);
int cnt = 0;
int cMinR = pos[0].fi;
int cMaxR = pos[0].fi;
int cMinC = pos[0].se;
int cMaxC = pos[0].se;
int i = 0;
while(1) {
if(cMinR == 0 && cMaxR == h-1 && cMinC == 0 && cMaxC == w-1) break;
i = (cMaxR-cMinR+1)*(cMaxC-cMinC+1)-1;
cMinR = SEGMINR.get(0,i);
cMaxR = SEGMAXR.get(0,i);
cMinC = SEGMINC.get(0,i);
cMaxC = SEGMAXC.get(0,i);
i++;
if(i == (cMaxR-cMinR+1)*(cMaxC-cMinC+1)) cnt++;
i = (cMaxR-cMinR+1)*(cMaxC-cMinC+1);
cMinR = SEGMINR.get(0,i);
cMaxR = SEGMAXR.get(0,i);
cMinC = SEGMINC.get(0,i);
cMaxC = SEGMAXC.get(0,i);
}
cnt++; // everything
return cnt;
}
