#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1e9 + 7;
struct segment_tree{
static pair <int, int> merge(const pair <int, int>& lhs, const pair <int, int>& rhs){
return pair{min(lhs.first, rhs.first), max(lhs.second, rhs.second)};
}
static constexpr auto unit = pair{inf, -inf};
vector <pair <int, int>> seg;
segment_tree(){ }
segment_tree(int n){
int sz = 1;
while (sz < n * 2){
sz *= 2;
}
seg.assign(sz, unit);
}
void build(int id, int l, int r, const vector <int>& a){
if (l == r){
seg[id] = pair{a[l], a[l]};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid, a);
build(id * 2 + 1, mid + 1, r, a);
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
}
void update(int id, int l, int r, int i, int x){
if (l == r){
seg[id] = pair{x, x};
return;
}
int mid = (l + r) >> 1;
if (i <= mid){
update(id * 2, l, mid, i, x);
}
else{
update(id * 2 + 1, mid + 1, r, i, x);
}
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
}
pair <int, int> query(int id, int l, int r, int u, int v){
if (v < l or r < u){
return unit;
}
if (u <= l and r <= v){
return seg[id];
}
int mid = (l + r) >> 1;
return merge(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
}
};
struct bounding_rectangle{
int lx = inf, rx = -inf, ly = inf, ry = -inf;
void insert(int x, int y){
lx = min(lx, x);
rx = max(rx, x);
ly = min(ly, y);
ry = max(ry, y);
}
int area(){
return (rx - lx + 1) * (ry - ly + 1);
}
};
int n, m;
vector <int> pos_x, pos_y;
segment_tree seg_x, seg_y;
void give_initial_chart(int _n, int _m, vector <int> _r, vector <int> _c){
n = _n;
m = _m;
pos_x.resize(n * m);
pos_y.resize(n * m);
for (int val = 0; val < n * m; val++){
int x = _r[val], y = _c[val];
pos_x[val] = x;
pos_y[val] = y;
}
seg_x = segment_tree(n * m);
seg_x.build(1, 0, n * m - 1, pos_x);
seg_y = segment_tree(n * m);
seg_y.build(1, 0, n * m - 1, pos_y);
}
int swap_seats(int val1, int val2){
{
int x1 = pos_x[val1], x2 = pos_x[val2];
swap(pos_x[val1], pos_x[val2]);
int y1 = pos_y[val1], y2 = pos_y[val2];
swap(pos_y[val1], pos_y[val2]);
seg_x.update(1, 0, n * m - 1, val1, x2);
seg_x.update(1, 0, n * m - 1, val2, x1);
seg_y.update(1, 0, n * m - 1, val1, y2);
seg_y.update(1, 0, n * m - 1, val2, y1);
}
int ans = 0;
int ptr = 0;
while (ptr < n * m){
auto [lx, rx] = seg_x.query(1, 0, n * m - 1, 0, ptr);
auto [ly, ry] = seg_y.query(1, 0, n * m - 1, 0, ptr);
if ((rx - lx + 1) * (ry - ly + 1) == ptr + 1){
ans++;
ptr++;
}
else{
ptr = (rx - lx + 1) * (ry - ly + 1) - 1;
}
}
return ans;
}
