#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 1E6+16;
ii wh[MAXN];
vll mat[MAXN];
ll n;
ll h, w;
#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
struct Node {
ll minN;
ll couN;
ll lazy;
Node operator+ (const Node &o) const {
return {
min(minN, o.minN),
(minN <= o.minN ? couN : 0) + (o.minN <= minN ? o.couN : 0),
0
};
}
};
vector <Node> tree;
ll n;
void init (ll n) {
tree.assign(2*n, Node{ 0, 1, 0 });
SegTree::n = n;
dfs_init(0, n-1, 0);
}
void dfs_init (ll l, ll r, ll id) {
if (l == r) return;
dfs_init(l, mid, id+1);
dfs_init(mid+1, r, id+off);
tree[id] = tree[id+1] + tree[id+off];
}
void push (ll l, ll r, ll id) {
if (!tree[id].lazy) return;
tree[id].minN += tree[id].lazy;
if (l < r) {
tree[id+1].lazy += tree[id].lazy;
tree[id+off].lazy += tree[id].lazy;
}
tree[id].lazy = 0;
}
void update (ll ql, ll qr, ll val) { update(ql, qr, val, 0, n-1, 0); }
void update (ll ql, ll qr, ll val, ll l, ll r, ll id) {
push(l, r, id);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree[id].lazy = val;
push(l, r, id);
return;
}
update(ql, qr, val, l, mid, id+1);
update(ql, qr, val, mid+1, r, id+off);
tree[id] = tree[id+1] + tree[id+off];
}
Node query () {
push(0, n-1, 0);
return tree[0];
}
} st;
vii intervs (ll i, ll j) {
assert(0 <= i && i <= h);
assert(0 <= j && j <= w);
vii nums;
if (i > 0 && j > 0)
nums.push_back({ mat[i-1][j-1], 0 });
else
nums.push_back({ n, 0 });
if (i > 0 && j < w)
nums.push_back({ mat[i-1][j], 1 });
else
nums.push_back({ n, 1 });
if (i < h && j > 0)
nums.push_back({ mat[i][j-1], 2 });
else
nums.push_back({ n, 2 });
if (i < h && j < w)
nums.push_back({ mat[i][j], 3 });
else
nums.push_back({ n, 3 });
sort(nums.begin(), nums.end());
vii ans;
if ((nums[0].second ^ nums[1].second) == 3) { // opposite corners in first, second turned on
ans.push_back({ nums[0].first, nums[3].first-1 });
} else {
ans.push_back({ nums[0].first, nums[1].first-1 });
ans.push_back({ nums[2].first, nums[3].first-1 });
}
return ans;
}
void give_initial_chart (int h, int w, vi r, vi c) {
::h = h, ::w = w;
n = h*w;
st.init(n);
for (ll i = 0; i < n; i++) {
wh[i] = ii{ r[i], c[i] };
}
for (ll i = 0; i < n; i++) {
mat[r[i]].push_back(i);
}
for (ll i = 0; i < h; i++) {
sort(mat[i].begin(), mat[i].end(), [&](ll a, ll b) {
return c[a] < c[b];
});
}
for (ll i = 0; i <= h; i++) {
for (ll j = 0; j <= w; j++) {
for (auto [l, r] : intervs(i, j)) {
st.update(l, r, +1);
}
}
}
}
int swap_seats (int a, int b) {
auto [ai, aj] = wh[a];
auto [bi, bj] = wh[b];
vii mySet;
mySet.push_back({ ai, aj });
mySet.push_back({ ai, aj+1 });
mySet.push_back({ ai+1, aj });
mySet.push_back({ ai+1, aj+1 });
mySet.push_back({ bi, bj });
mySet.push_back({ bi, bj+1 });
mySet.push_back({ bi+1, bj });
mySet.push_back({ bi+1, bj+1 });
sort(mySet.begin(), mySet.end());
mySet.resize(unique(mySet.begin(), mySet.end()) - mySet.begin());
for (auto [i, j] : mySet)
for (auto [l, r] : intervs(i, j))
st.update(l, r, -1);
swap(wh[a], wh[b]);
swap(mat[ai][aj], mat[bi][bj]);
for (auto [i, j] : mySet)
for (auto [l, r] : intervs(i, j))
st.update(l, r, +1);
return st.query().couN;
}
