#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=1e6+5;
const array<int,4> inf={(int)1e9,0,(int)1e9,0};
int H,W;
vector<int> R,C;
array<int,4> arr[MX];
struct segtree {
array<int,4> t[4*MX];
array<int,4> merge(array<int,4> l, array<int,4> r) {
return {min(l[0],r[0]),max(l[1],r[1]),min(l[2],r[2]),max(l[3],r[3])};
}
void upd(int v, int l, int r, int pos, array<int,4> val) {
if(l>r) return;
if(pos<l || r<pos) return;
if(l==r) {
t[v]=val;
return;
}
int m=(l+r)/2;
upd(v*2+0,l,m+0,pos,val);
upd(v*2+1,m+1,r,pos,val);
t[v]=merge(t[2*v+0],t[2*v+1]);
}
array<int,4> que(int v, int l, int r, int ql, int qr) {
if(r<ql || qr<l) return inf;
if(ql<=l && r<=qr) return t[v];
int m=(l+r)/2;
return merge(que(v*2+0,l,m+0,ql,qr),que(v*2+1,m+1,r,ql,qr));
}
vector<pair<int,int>> dfs(int v, int l, int r, array<int,4> cur) {
if(l>r) return {};
if(t[v]==inf) return {};
if(l==r) {
array<int,4> nxt=merge(cur,arr[l]);
return {{l,(nxt[1]-nxt[0]+1)*(nxt[3]-nxt[2]+1)}};
}
int m=(l+r)/2;
vector<pair<int,int>> res;
if(cur!=merge(cur,t[2*v])) {
vector<pair<int,int>> res2=dfs(2*v,l,m,cur);
for(auto x:res2) res.push_back(x);
res2.clear();
}
array<int,4> nxt=merge(cur,t[2*v]);
if(nxt!=merge(nxt,t[2*v+1])) {
vector<pair<int,int>> res2=dfs(2*v+1,m+1,r,nxt);
for(auto x:res2) res.push_back(x);
res2.clear();
}
return res;
}
void prep() {
for(int i=0;i<4*MX;i++) {
t[i]=inf;
}
}
} st;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
::H=H, ::W=W, ::R=R, ::C=C;
st.prep();
for(int i=0;i<H*W;i++) {
arr[i]={R[i],R[i],C[i],C[i]};
st.upd(1,0,H*W-1,i,arr[i]);
}
}
int swap_seats(int a, int b) {
swap(arr[a],arr[b]);
st.upd(1,0,H*W-1,a,arr[a]);
st.upd(1,0,H*W-1,b,arr[b]);
vector<pair<int,int>> v=st.dfs(1,0,H*W-1,inf);
v.push_back({H*W,(int)1e9});
int ans=0;
for(int i=0;i+1<v.size();i++) {
int x=v[i].first, y=v[i+1].first;
int area=v[i].second;
ans+=x<area && area<=y;
}
return ans;
}
