#include "seats.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<int>> grid;
unordered_map<int,pair<int,int>> pos;
vector<pair<pair<int,int>,pair<int,int>>> sq;
int init_cnt=0;
vector<bool> cnt;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
grid.resize(H,vector<int>(W));
sq.resize(W*H);
cnt.resize(W*H);
for (int i = 0; i < H*W; i++)
{
grid[R[i]][C[i]]=i;
pos[i]={R[i],C[i]};
}
int mxR=0, mnL=1e9;
int mnH=1e9, mxD=0;
for (int i = 0; i < H*W; i++)
{
mxR=max(C[i],mxR);
mxD=max(R[i],mxD);
mnL=min(C[i],mnL);
mnH=min(R[i],mnH);
int sz=(mxR-mnL+1)*(mxD-mnH+1);
if(sz<=i+1) { init_cnt++; cnt[i]=true; }
sq[i]={{mnL,mxR},{mnH,mxD}};
}
}
int swap_seats(int a, int b){
if(b<a) swap(a,b);
pair<int,int> posA=pos[a];
grid[pos[a].first][pos[a].second]=a;
grid[pos[b].first][pos[b].second]=b;
pos[a]=pos[b];
pos[b]=posA;
int mxR=0, mnL=1e9;
int mnH=1e9, mxD=0;
if(a>0){
mxR=sq[a].first.first;
mnL=sq[a].first.second;
mnH=sq[a].second.first;
mxD=sq[a].second.second;
}
for (int i = a; i <= b; i++)
{
init_cnt-=cnt[i];
cnt[i]=0;
mxR=max(pos[i].second,mxR);
mxD=max(pos[i].first,mxD);
mnL=min(pos[i].second,mnL);
mnH=min(pos[i].first,mnH);
int sz=(mxR-mnL+1)*(mxD-mnH+1);
if(sz<=i+1) { init_cnt++; cnt[i]=true; }
sq[i]={{mnL,mxR},{mnH,mxD}};
}
return init_cnt;
}
