#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 1e6 + 5;
const int BLOCK = 200;
const int BLOCKCNT = MAX / BLOCK + 3;
const int oo = 1e9 + 9;
int n;
int h, w;
pii mp[MAX];
struct DATA{
map<int, int> mpX, mpY;
void add(pii a){
mpX[a.first]++;
mpY[a.second]++;
}
void remove(pii a){
mpX[a.first]--;
if(mpX[a.first] == 0) mpX.erase(a.first);
mpY[a.second]--;
if(mpY[a.second] == 0) mpY.erase(a.second);
}
array<int, 4> get(){
return {mpX.begin()->first, mpY.begin()->first, prev(mpX.end())->first, prev(mpY.end())->first};
}
};
DATA blocks[BLOCKCNT];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = R.size();
h = H;
w = W;
for (int i = 0; i < n; i++)
{
mp[i] = {R[i], C[i]};
}
int p = 0;
for (int i = 0; i < n; i++)
{
blocks[p].add({R[i], C[i]});
if(i % BLOCK == 0){
++p;
blocks[p].mpX = blocks[p - 1].mpX;
blocks[p].mpY = blocks[p - 1].mpY;
}
}
}
int swap_seats(int a, int b) {
if(a > b) swap(a, b);
int aBLOCK = (a + BLOCK - 1) / BLOCK;
int bBLOCK = (b + BLOCK - 1) / BLOCK;
for (int i = aBLOCK; i < bBLOCK; i++)
{
blocks[i].remove(mp[a]);
blocks[i].add(mp[b]);
}
swap(mp[a], mp[b]);
int mnR = oo, mxR = -oo, mnC = oo, mxC = -oo;
int ans = 0;
for (int i = 0; i < n; i++)
{
if(i % BLOCK == 0){
array<int, 4> a = blocks[i / BLOCK].get();
mxR = max(mxR, a[2]);
mxC = max(mxC, a[3]);
mnR = min(mnR, a[0]);
mnC = min(mnC, a[1]);
}
else{
mxR = max(mxR, mp[i].first);
mxC = max(mxC, mp[i].second);
mnR = min(mnR, mp[i].first);
mnC = min(mnC, mp[i].second);
}
int r = mxR - mnR + 1;
int c = mxC - mnC + 1;
if(r * c == i + 1){
ans++;
}
if(r * c - (i + 1) >= BLOCK){
i = (i + BLOCK) / BLOCK * BLOCK - 1;
}
}
return ans;
}
