#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
struct seat
{
int r, c;
};
seat s[maxn];
int h, w;
set < int > row[maxn], col[maxn];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
h = H;
w = W;
for (int i = 0; i < h * w; i ++)
{
s[i].r = R[i];
s[i].c = C[i];
row[R[i]].insert(i);
col[C[i]].insert(i);
}
}
struct event
{
int val, type, tp;
event(int _type = -1, int _val = -1, int _tp = -1)
{
type = _type;
val = _val;
tp = _tp;
}
};
bool cmp(const event &e1, const event &e2)
{
return e1.tp < e2.tp;
}
int swap_seats(int a, int b)
{
row[s[a].r].erase(a);
row[s[b].r].erase(b);
col[s[a].c].erase(a);
col[s[b].c].erase(b);
swap(s[a], s[b]);
row[s[a].r].insert(a);
row[s[b].r].insert(b);
col[s[a].c].insert(a);
col[s[b].c].insert(b);
vector < event > ev;
vector < pair < int, int > > rx;
for (int i = 0; i < h; i ++)
{
if (row[i].size() == 0)
continue;
rx.push_back({*row[i].begin(), i});
}
sort(rx.begin(), rx.end());
ll max_row = -1e9, min_row = 1e9;
for (int i = 0; i < rx.size(); i ++)
{
if (rx[i].second > max_row)
{
max_row = rx[i].second;
ev.push_back(event(0, rx[i].second, rx[i].first));
}
if (rx[i].second < min_row)
{
min_row = rx[i].second;
ev.push_back(event(1, rx[i].second, rx[i].first));
}
}
vector < pair < int, int > > cx;
for (int i = 0; i < w; i ++)
{
if (col[i].size() == 0)
continue;;
cx.push_back({*col[i].begin(), i});
}
sort(cx.begin(), cx.end());
ll max_col = -1e9, min_col = 1e9;
for (int i = 0; i < cx.size(); i ++)
{
if (cx[i].second > max_col)
{
max_col = cx[i].second;
ev.push_back(event(2, cx[i].second, cx[i].first));
}
if (cx[i].second < min_col)
{
min_col = cx[i].second;
ev.push_back(event(3, cx[i].second, cx[i].first));
}
}
sort(ev.begin(), ev.end(), cmp);
min_col = 1e9;
max_col = -1e9;
min_row = 1e9;
max_row = -1e9;
int ans = 1;
for (int i = 0; i < ev.size(); i ++)
{
if (i != 0 && ev[i - 1].tp != ev[i].tp)
{
if ((max_row - min_row + 1) * (max_col - min_col + 1) ==
ev[i].tp)
ans ++;
}
if (ev[i].type == 0)
{
max_row = ev[i].val;
}
else
if (ev[i].type == 1)
{
min_row = ev[i].val;
}
else
if (ev[i].type == 2)
{
max_col = ev[i].val;
}
else
if (ev[i].type == 3)
{
min_col = ev[i].val;
}
}
return ans;
}
