#include "seats.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
void operator+=(pair<int,int>&a,pair<int,int>b){
a.first+=b.first,a.second+=b.second;
}
struct segtree{
struct DDT{
pair<int,int>mn,lz;
int mnc,l,r;
DDT(){mnc=1,mn=lz={0,0};}
DDT(DDT a,DDT b){
*this=a;
if(b.mn<mn)
mn=b.mn,mnc=0;
if(b.mn==mn)
mnc+=b.mnc;
}
} T[1<<21];
void pd(int i){
pair<int,int>k=T[i].lz;
if(k.first||k.second){
T[i].lz={0,0},
T[i].mn+=k;
if(i<1<<20)
T[i*2].lz+=k,
T[i*2+1].lz+=k;
}
}
void upd(int i,int l,int r,int ll,int rr,pair<int,int> v){
T[i].l=l,T[i].r=r;
pd(i);if(ll<=l&&r<=rr)
return T[i].lz=v,pd(i);
if(ll>r||l>rr) return;
upd(i*2,l,l+r>>1,ll,rr,v);
upd(i*2+1,l+r+2>>1,r,ll,rr,v);
T[i]=DDT(T[i*2],T[i*2+1]);
}
} ST;
vector<int>c,r;
vector<vector<int>>app;
int CN;
bitset<1000100>had;
inline void dostuf(int x,int y,int l,int r,int coef){
vector<int>v;
for(int i=0;i<2;i++) for(int j=0;j<2;j++)
v.push_back(min(r,max(l,app[x+i][y+j])));
sort(v.begin(),v.end());
ST.upd(1,1,CN,v[0],v[1]-1,{coef,0});
ST.upd(1,1,CN,v[2],v[3]-1,{0,coef});
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
CN=H*W;
app.resize(H+2,vector<int>(W+2,1e9));
for(auto&i:C)i++;
for(auto&i:R)i++;
C.insert(C.begin(),0);
R.insert(R.begin(),0);
c=C;r=R;
for(int i=1;i<=H*W;i++)
app[R[i]][C[i]]=i;
for(int i=0;i<=H;i++)
for(int j=0;j<=W;j++)
dostuf(i,j,1,CN+1,1);
}
set<pair<int,int>>S;
inline void do_contrib(int l,int r,int coef){
for(auto [i,j]:S)
dostuf(i,j,l,r,coef);
}
int swap_seats(int a, int b) {
a++;b++; if(a>b)swap(a,b);
S.clear();
for(int i=0;i<2;i++) for(int j=0;j<2;j++)
S.insert({r[a]-i,c[a]-j}),S.insert({r[b]-i,c[b]-j});
do_contrib(a,b,-1);
swap(c[a],c[b]);
swap(r[a],r[b]);
app[r[a]][c[a]]=a;
app[r[b]][c[b]]=b;
do_contrib(a,b,1);
return ST.T[1].mnc;
}
