#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int>pii;
int n;
struct node{
int mn = 1e9,mx = -1e9;
node(){}
};
struct seg{
vector<int>a;
vector<node>t;
int N;
void build(int v,int l,int r){
if(l==r){
t[v].mn = t[v].mx = a[l];
return;
}
int tm = (l+r)/2;
build(2*v,l,tm);
build(2*v+1,tm+1,r);
t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
}
seg(){}
seg(int _N,vector<int>_a){
N = _N;
a = _a;
t.resize(4*N);
build(1,0,N-1);
}
void upd(int v,int pos,int l,int r,int val){
if(l==r){
t[v].mn = t[v].mx = val;
return;
}
int tm = (l+r)/2;
if(pos<=tm)upd(2*v,pos,l,tm,val);
else upd(2*v+1,pos,tm+1,r,val);
t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
}
pii query(int v,int l,int r,int tl,int tr){
if(l>r)return {1e9,-1e9};
if(l == tl && r == tr)return {t[v].mn,t[v].mx};
int tm = (tl+tr)/2;
pii a = query(2*v,l,min(r,tm),tl,tm);
pii b = query(2*v+1,max(l,tm+1),r,tm+1,tr);
pii c;
c.fi = min(a.fi,b.fi);
c.se = max(a.se,b.se);
return c;
}
}rr,cc;
vector<int>r,c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
r = R;
c = C;
rr = seg(n,r);
cc = seg(n,c);
}
int swap_seats(int a, int b) {
swap(r[a],r[b]);
swap(c[a],c[b]);
rr.upd(1,a,0,n-1,r[a]);
cc.upd(1,a,0,n-1,c[a]);
rr.upd(1,b,0,n-1,r[b]);
cc.upd(1,b,0,n-1,c[b]);
int ans = 0;
for(int i=0;i<n;){
pii x = rr.query(1,0,i,0,n-1);
pii y = cc.query(1,0,i,0,n-1);
// cout<<i<<" "<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<'\n';
if((x.se-x.fi+1) * (y.se - y.fi+1) == i+1){
ans++;
i+=min(x.se - x.fi+1,y.se - y.fi+1);
}else i = (x.se-x.fi+1) * (y.se - y.fi+1) - 1;
}
return ans;
}
