#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
class SegmentTree {
private:
struct Node {
int mn, mx;
Node () {
mx = -1e9;
mn = 1e9;
}
void merge(Node esq, Node dir) {
mn = min(esq.mn, dir.mn);
mx = max(esq.mx, dir.mx);
}
};
int LO, HI;
vector<Node> seg;
void build(int l, int r, int node, const vector<int> &arr) {
if (l == r) {
seg[node].mn = seg[node].mx = arr[l];
return;
}
const int mid = l + (r - l) / 2;
build(l, mid, 2 * node + 1, arr);
build(mid + 1, r, 2 * node + 2, arr);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
void modify(int l, int r, int where, int delta, int node) {
if (l > where || r < where) return;
if (l >= where && r <= where) {
seg[node].mn = seg[node].mx = delta;
return;
}
const int mid = l + (r - l) / 2;
modify(l, mid, where, delta, 2 * node + 1);
modify(mid + 1, r, where, delta, 2 * node + 2);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
Node query(int ql, int qr, int l, int r, int node) {
if (l > qr || r < ql) return Node();
if (l >= ql && r <= qr) return seg[node];
const int mid = l + (r - l) / 2;
Node esq = query(ql, qr, l, mid, 2 * node + 1);
Node dir = query(ql, qr, mid + 1, r, 2 * node + 2);
Node ans;
ans.merge(esq, dir);
return ans;
}
public:
void build(const vector<int> &arr) {
LO = 0;
HI = (int) arr.size() - 1;
seg.clear();
seg.resize(4 * (int)arr.size());
build(LO, HI, 0, arr);
}
void modify(int where, int delta) {
modify(LO, HI, where, delta, 0);
}
pair<int, int> query(int ql, int qr) {
Node ans = query(ql, qr, LO, HI, 0);
return {ans.mn, ans.mx};
}
};
SegmentTree linhas, colunas;
int r, c;
vector<pair<int, int>> where;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
ios::sync_with_stdio(0);
cin.tie(0);
r = H;
c = W;
linhas.build(R);
colunas.build(C);
where.resize(r * c);
for (int i = 0; i < r * c; i++) {
where[i] = {R[i], C[i]};
}
}
int solve() {
int res = 0;
int min_row = 1e9;
int max_row = -1e9;
int min_column = 1e9;
int max_column = -1e9;
for (int i = 0; i < r * c; ) {
pair<int, int> line = linhas.query(0, i);
min_row = min(min_row, line.first);
max_row = max(max_row, line.second);
pair<int, int> col = colunas.query(0, i);
min_column = min(min_column, col.first);
max_column = max(max_column, col.second);
const int cur = ((max_row - min_row + 1) * (max_column - min_column + 1));
if (cur == i + 1) {
++res;
++i;
} else {
i = cur - 1;
}
}
return res;
}
int swap_seats(int a, int b) {
const int a_linha = where[a].first;
const int b_linha = where[b].first;
linhas.modify(a, b_linha);
linhas.modify(b, a_linha);
const int a_coluna = where[a].second;
const int b_coluna = where[b].second;
colunas.modify(a, b_coluna);
colunas.modify(b, a_coluna);
swap(where[a], where[b]);
return solve();
}
