#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int const inf = 0x3f3f3f3f;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vector<int>>;
int n, m;
vii pos;
vvi v;
struct Seg {
int n;
vector<int> tree;
vector<int> v;
Seg(vi const& v) : n(v.size()), tree(n*4), v(v) {
build(0, 0, n-1);
};
void build(int no, int l, int r) {
if (l == r) return void(tree[no] = v[l]);
int m = (l+r)/2;
build(no*2+1, l, m);
build(no*2+2, m+1, r);
tree[no] = max(tree[no*2+1], tree[no*2+2]);
}
void upd(int no, int l, int r, int pos, int val) {
if (l == r) return void(tree[no] = val);
int m = (l+r)/2;
if (pos <= m) upd(no*2+1, l, m, pos, val);
else upd(no*2+2, m+1, r, pos, val);
tree[no] = max(tree[no*2+1], tree[no*2+2]);
}
int get(int no, int l, int r, int a, int b) {
if (a <= l and r <= b) return tree[no];
int m = (l+r)/2;
if (b <= m) return get(no*2+1, l, m, a, b);
if (a > m) return get(no*2+2, m+1, r, a, b);
return max(get(no*2+1, l, m, a, b),
get(no*2+2, m+1, r, a, b));
}
};
vector<Seg> rows, cols;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H, m = W;
v = vvi(n, vi(m));
for (int i = 0; i < n*m; i++) {
v[R[i]][C[i]] = i;
pos.emplace_back(R[i], C[i]);
}
for (int i = 0; i < n; i++) {
rows.emplace_back(v[i]);
}
vector<int> col;
for (int i = 0; i < m; i++) {
col.clear();
for (int j = 0; j < n; j++) {
col.push_back(v[j][i]);
}
cols.emplace_back(col);
}
}
int swap_seats(int a, int b) {
swap(pos[a], pos[b]);
rows[pos[a].first].upd(0, 0, m-1, pos[a].second, a);
rows[pos[b].first].upd(0, 0, m-1, pos[b].second, b);
cols[pos[a].second].upd(0, 0, n-1, pos[a].first, a);
cols[pos[b].second].upd(0, 0, n-1, pos[b].first, b);
int x1, x2, y1, y2;
x1 = x2 = pos[0].first;
y1 = y2 = pos[0].second;
int max_at = 0;
int ans = 1;
struct Result {
int maxi, x1, x2, y1, y2;
bool operator<(Result const& rhs) const {
return maxi < rhs.maxi;
}
};
Result rs[4];
for (int i = 1; i < n + m - 1; i++) {
fill(rs, rs+4, Result{inf, 0, 0, 0, 0});
if (x1 > 0)
rs[0] = {max(max_at, rows[x1-1].get(0, 0, m-1, y1, y2)),
x1-1, x2, y1, y2};
if (x2+1 < n)
rs[1] = {max(max_at, rows[x2+1].get(0, 0, m-1, y1, y2)),
x1, x2+1, y1, y2};
if (y1 > 0)
rs[2] = {max(max_at, cols[y1-1].get(0, 0, n-1, x1, x2)),
x1, x2, y1-1, y2};
if (y2+1 < m)
rs[3] = {max(max_at, cols[y2+1].get(0, 0, n-1, x1, x2)),
x1, x2, y1, y2+1};
Result res = *min_element(rs, rs+4);
x1 = res.x1;
x2 = res.x2;
y1 = res.y1;
y2 = res.y2;
max_at = res.maxi;
if (max_at == (x2-x1+1)*(y2-y1+1) - 1) ans++;
}
return ans;
}
