#include "seats.h"
#include <bits/stdc++.h>
template <class M>
class LazySegmentTree {
using T = typename M::T;
using L = typename M::L;
int n, size, logn;
std::vector<T> data;
std::vector<L> lazy;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
void all_apply(int i, const L &f) {
data[i] = M::map(f, data[i]);
if (i < size) lazy[i] = M::composite(f, lazy[i]);
}
void push(int i) {
all_apply(2 * i, lazy[i]);
all_apply(2 * i + 1, lazy[i]);
lazy[i] = M::id();
}
public:
LazySegmentTree() {}
LazySegmentTree(const std::vector<T> &vec) {
n = (int)vec.size();
logn = 1;
while ((1 << logn) < n) ++logn;
size = 1 << logn;
data.assign(2 * size, M::e());
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i >= 1; --i) update(i);
lazy.assign(size, M::id());
}
void apply(int l, int r, const L &f) {
l += size;
r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l /= 2;
r /= 2;
}
l = l2;
r = r2;
for (int d = 1; d <= logn; ++d) {
if (((l >> d) << d) != l) update(l >> d);
if (((r >> d) << d) != r) update((r - 1) >> d);
}
}
T fold(int l, int r) {
l += size;
r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
T pl = M::e(), pr = M::e();
while (l < r) {
if (l & 1) pl = M::op(pl, data[l++]);
if (r & 1) pr = M::op(data[--r], pr);
l /= 2;
r /= 2;
}
return M::op(pl, pr);
}
};
constexpr int inf = 1 << 30;
struct MCountMin {
struct T {
int mn, cnt;
};
static T op(T a, T b) {
if (a.mn == b.mn) return {a.mn, a.cnt + b.cnt};
return a.mn < b.mn ? a : b;
}
static T e() {
return {inf, 0};
}
struct L {
int ad;
};
static T map(L a, T b) {
return {b.mn + a.ad, b.cnt};
}
static L composite(L a, L b) {
return {a.ad + b.ad};
}
static L id() {
return {0};
}
};
template <class M>
class SegmentTree {
using T = typename M::T;
int n, size;
std::vector<T> data;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
public:
SegmentTree() {}
SegmentTree(const std::vector<T> &vec) {
n = (int)vec.size();
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size, M::e());
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i >= 1; --i) update(i);
}
void set(int i, const T &v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
update(i);
}
}
T fold(int l, int r) {
T pl = M::e(), pr = M::e();
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l & 1) pl = M::op(pl, data[l++]);
if (r & 1) pr = M::op(data[--r], pr);
}
return M::op(pl, pr);
}
};
struct MonoidMinMax {
using T = std::pair<int, int>;
static T op(const T &a, const T &b) {
return {std::min(a.first, b.first), std::max(a.second, b.second)};
}
static T e() {
return {inf, -1};
}
};
int H, W;
std::vector<int> R, C;
// SegmentTree<MonoidMinMax> rowSeg, colSeg;
LazySegmentTree<MCountMin> seg;
std::vector<std::set<int>> rowIds, colIds;
std::vector<std::pair<int, bool>> firstIds;
std::vector<int> times;
void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) {
H = h;
W = w;
R = r;
C = c;
assert(H == 1);
times.resize(W);
for (int i = 0; i < W; ++i) {
times[c[i]] = i;
}
seg = LazySegmentTree<MCountMin>(std::vector<typename MCountMin::T>(W, {0, 1}));
for (int i = -1; i < W; ++i) {
int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
if (x > y) std::swap(x, y);
seg.apply(x, y, {1});
}
/*
rowSeg = SegmentTree<MonoidMinMax>(rInit);
colSeg = SegmentTree<MonoidMinMax>(cInit);
rowIds.resize(H);
colIds.resize(W);
for (int i = 0; i < H * W; ++i) {
if (colIds[C[i]].empty()) {
firstIds.push_back({i, false});
}
colIds[C[i]].insert(i);
if (rowIds[R[i]].empty()) {
firstIds.push_back({i, true});
}
rowIds[R[i]].insert(i);
}
*/
}
void updRow(int i, int v, bool b) {
if (not rowIds[i].empty()) {
int mi = *rowIds[i].begin();
auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
firstIds.erase(itr);
}
if (b) rowIds[i].insert(v);
else rowIds[i].erase(v);
if (rowIds[i].empty()) return;
int mi = *rowIds[i].begin();
auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
firstIds.insert(itr, {mi, true});
}
void updCol(int i, int v, bool b) {
if (not colIds[i].empty()) {
int mi = *colIds[i].begin();
auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
firstIds.erase(itr);
}
if (b) colIds[i].insert(v);
else colIds[i].erase(v);
if (colIds[i].empty()) return;
int mi = *colIds[i].begin();
auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
firstIds.insert(itr, {mi, false});
}
void eraseI(int i) {
int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
if (x > y) std::swap(x, y);
seg.apply(x, y, {-1});
}
void addI(int i) {
int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
if (x > y) std::swap(x, y);
seg.apply(x, y, {1});
}
int swap_seats(int a, int b) {
// upd
/*
updRow(R[a], a, false);
updCol(C[a], a, false);
updRow(R[b], b, false);
updCol(C[b], b, false);
updRow(R[a], b, true);
updCol(C[a], b, true);
updRow(R[b], a, true);
updCol(C[b], a, true);
rowSeg.set(a, std::make_pair(R[b], R[b]));
rowSeg.set(b, std::make_pair(R[a], R[a]));
colSeg.set(a, std::make_pair(C[b], C[b]));
colSeg.set(b, std::make_pair(C[a], C[a]));
*/
eraseI(C[a]);
eraseI(C[a] - 1);
eraseI(C[b]);
eraseI(C[b] - 1);
std::swap(times[C[a]], times[C[b]]);
// std::swap(R[a], R[b]);
std::swap(C[a], C[b]);
addI(C[a]);
addI(C[a] - 1);
addI(C[b]);
addI(C[b] - 1);
const auto res = seg.fold(0, W);
return res.cnt;
// calc
/*
int answer = 0;
int last = 0;
for (const auto [i, b] : firstIds) {
// at i - 1
if (last == i) {
continue;
}
const auto x = rowSeg.fold(0, i), y = colSeg.fold(0, i);
if ((x.second - x.first + 1) * (y.second - y.first + 1) == i) {
++answer;
}
last = i;
}
++answer;
*/
}
