// Be name khode //
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int maxn = 1e6 + 10;
const int maxnt = 4e6 + 10;
const int lg = 20;
std::vector<int> r;
int n, m, have = 0;
pair <ll, ll> a[maxn];
pair<int, pair<int, ll>> av[maxn];
set <int> avR[maxn], avC[maxn];
int mnR[maxn], mnC[maxn];
bool mark[maxn];
pair <pair<int, int>, pair<int, int>> seg[maxnt];
pair <pair<int, int>, pair<int, int>> comb(pair <pair<int, int>, pair<int, int>> a, pair <pair<int, int>, pair<int, int>> b){
return {{max(a.fi.fi, b.fi.fi), min(a.fi.se, b.fi.se)}, {max(a.se.fi, b.se.fi), min(a.se.se, b.se.se)}};
}
void upd(int l, int r, int id, int v){
if(r - l == 1){
seg[v] = {{a[id].fi, a[id].fi}, {a[id].se, a[id].se}};
return;
}
int mid = (l + r) >> 1;
if(id < mid)
upd(l, mid, id, v * 2);
else
upd(mid, r, id, v * 2 + 1);
seg[v] = comb(seg[v * 2], seg[v * 2 + 1]);
}
pair <pair<int, int>, pair<int, int>> get(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return {{-1, maxn}, {-1, maxn}};
if(lq <= l && r <= rq)
return seg[v];
int mid = (l + r) >> 1;
return comb(get(l, mid, lq, rq, v * 2), get(mid, r, lq, rq, v * 2 + 1));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
for(int i = 0; i < n * m; i++){
a[i] = {R[i], C[i]};
avR[a[i].fi].insert(i);
avC[a[i].se].insert(i);
}
fill(mnR, mnR + n + 5, n * m + 2);
fill(mnC, mnC + m + 5, n * m + 2);
for(int i = 0; i < n; i++) if(avR[i].size())
mnR[i] = *avR[i].begin();
for(int i = 0; i < m; i++) if(avC[i].size())
mnC[i] = *avC[i].begin();
pair <ll, ll> h, w;
h = {a[0].fi, a[0].fi};
w = {a[0].se, a[0].se};
int ans = 0;
for(int i = 0; i < n * m; i++){
h.fi = max(h.fi, a[i].fi);
h.se = min(h.se, a[i].fi);
w.fi = max(w.fi, a[i].se);
w.se = min(w.se, a[i].se);
if((h.fi - h.se + 1) * (w.fi - w.se + 1) == i + 1){
have++;
mark[i] = true;
}
}
}
void add(int id){
avR[a[id].fi].insert(id);
avC[a[id].se].insert(id);
mnR[a[id].fi] = min(mnR[a[id].fi], id);
mnC[a[id].se] = min(mnC[a[id].se], id);
}
void remo(int id){
avR[a[id].fi].erase(id);
avC[a[id].se].erase(id);
mnR[a[id].fi] = mnC[a[id].se] = n * m + 2;
if(avR[a[id].fi].size())
mnR[a[id].fi] = *avR[a[id].fi].begin();
if(avC[a[id].se].size())
mnC[a[id].se] = *avC[a[id].se].begin();
}
int swap_seats(int x, int y) {
if(n * m <= 10000 || max(n, m) <= 1000){
int ans = 0;
remo(x);
remo(y);
swap(a[x], a[y]);
add(x);
add(y);
int pt = 0;
for(int i = 0; i < n; i++) if(mnR[i] < n * m)
av[pt++] = {mnR[i], {0, i}};
for(int i = 0; i < m; i++) if(mnC[i] < n * m)
av[pt++] = {mnC[i], {1, i}};
sort(av, av + pt);
pair <ll, ll> h, w;
h = {-1, maxn};
w = h;
int last = -1;
//cout << av[0].fi << ' ' << av[0].se.fi << ' ' << av[0].se.se << endl;
//cout << av[1].fi << ' ' << av[1].se.fi << ' ' << av[1].se.se << endl;
for(int i = 0; i < pt; i++){
ll k = (h.fi - h.se + 1) * (w.fi - w.se + 1);
if(last > -1 && k >= last + 1 && k < av[i].fi + 1)
ans++;
/*
if(i == 2){
cout << "ha? " << h.fi << ' ' << h.se << ' ' << w.fi << ' ' << w.se << ' ' << k << ' ' << last << ' ' << av[i].fi << ' ' << ans << endl;
cout << pt << ' ' << (last > -1) << ' ' << (k >= last) << ' ' << (k < av[i].fi) << ' ' << k << ' ' << av[i].fi << endl;
}
*/
if(av[i].se.fi){
w.fi = max(w.fi, av[i].se.se);
w.se = min(w.se, av[i].se.se);
}
else{
h.fi = max(h.fi, av[i].se.se);
h.se = min(h.se, av[i].se.se);
}
last = av[i].fi;
}
//cout << ans << endl;
int k = (h.fi - h.se + 1) * (w.fi - w.se + 1);
if(k >= last + 1)
ans++;
//cout << last << ' ' << k << endl;
return ans;
}
swap(a[x], a[y]);
upd(0, n * m, x, 1);
upd(0, n * m, y, 1);
pair <ll, ll> h, w;
auto ret = get(0, n * m, 0, x, 1);
h = ret.fi;
w = ret.se;
for(int i = x; i <= y; i++){
if(mark[i]){
have--;
mark[i] = false;
}
h.fi = max(h.fi, a[i].fi);
h.se = min(h.se, a[i].fi);
w.fi = max(w.fi, a[i].se);
w.se = min(w.se, a[i].se);
if((h.fi - h.se + 1) * (w.fi - w.se + 1) == i + 1){
have++;
mark[i] = true;
}
}
return have;
}
