#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define lb lower_bound
#define pii pair<int,int>
#define F first
#define S second
#define in insert
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
const int MAX=1e6+10;
const int inf=1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int h,w;
vector<vector<int>> a;
struct node{
int mn,cnt;
node(){
mn=cnt=0;
}
};
node mrg(node a,node b){
node res;
if(a.mn<b.mn){
res=a;
}
else if(a.mn>b.mn){
res=b;
}
else{
res.mn=a.mn;
res.cnt=a.cnt+b.cnt;
}
return res;
}
struct segtree{
node t[4*MAX];
int add[4*MAX];
void build(int v,int tl,int tr){
add[v]=0;
if(tl==tr){
t[v].mn=0;
t[v].cnt=1;
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=mrg(t[2*v],t[2*v+1]);
}
void upd(int v,int x){
t[v].mn+=x;
add[v]+=x;
}
void push(int v){
if(add[v]){
upd(2*v,add[v]);
upd(2*v+1,add[v]);
add[v]=0;
}
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
upd(v,x);
return;
}
push(v);
int tm=(tl+tr)/2;
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
t[v]=mrg(t[2*v],t[2*v+1]);
}
int get(int v,int tl,int tr,int pos){
if(tl==tr){
return t[v].mn;
}
int tm=(tl+tr)/2;
push(v);
if(pos<=tm)return get(2*v,tl,tm,pos);
else return get(2*v+1,tm+1,tr,pos);
}
}T;
void upd(int i,int j,int x){
vector<int> v={a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]};
sort(all(v));
T.update(1,0,h*w-1,v[0],v[1]-1,x);
T.update(1,0,h*w-1,v[2],v[3]-1,x*10);
}
vector<int> r,c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h=H,w=W;
a.resize(h+2);
for(int i=0;i<=h+1;i++)a[i].resize(w+2);
for(int i=0;i<sz(R);i++){
R[i]++,C[i]++;
}
r=R,c=C;
for(int i=0;i<=h+1;i++){
for(int j=0;j<=w+1;j++){
a[i][j]=h*w;
}
}
for(int i=0;i<sz(R);i++){
a[R[i]][C[i]]=i;
}
T.build(1,0,h*w-1);
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
upd(i,j,1);
}
}
}
int swap_seats(int A,int B){
vector<pii> vec;
for(int i=r[A]-1;i<=r[A];i++){
for(int j=c[A]-1;j<=c[A];j++){
vec.pb({i,j});
}
}
for(int i=r[B]-1;i<=r[B];i++){
for(int j=c[B]-1;j<=c[B];j++){
vec.pb({i,j});
}
}
sort(all(vec));
vec.erase(unique(all(vec)),vec.end());
for(auto [i,j]:vec)upd(i,j,-1);
swap(a[r[A]][c[A]],a[r[B]][c[B]]);
swap(r[A],r[B]);
swap(c[A],c[B]);
for(auto [i,j]:vec)upd(i,j,1);
return T.t[1].cnt;
}
