#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const long long big = 1e7;
class Segtree {
private:
struct Node {
long long mn, c;
};
long long n; vector<Node> seg; vector<long long> lazy;
Node merge(Node &a, Node &b) {
if (a.mn < b.mn) return a;
if (a.mn > b.mn) return b;
return Node({a.mn, a.c + b.c});
}
public:
Segtree() {}
Segtree(int n) {
seg.resize(4 * n); lazy.resize(4 * n);
this->n = n;
build(1, 0, n - 1);
}
void build(int i, int l, int r) {
lazy[i] = 0;
if (l == r) {
seg[i] = {0, 1};
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void push(int i, int l, int r) {
if (!lazy[i]) return;
seg[i].mn += lazy[i];
if (l != r) {
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
}
lazy[i] = 0;
}
void upd(int i, int l, int r, int ql, int qr, long long qv) {
push(i, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lazy[i] += qv;
push(i, l, r);
return;
}
int mid = (l + r) / 2;
upd(i * 2, l, mid, ql, qr, qv);
upd(i * 2 + 1, mid + 1, r, ql, qr, qv);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void update(int ql, int qr, int qv) {
upd(1, 0, n - 1, ql, qr, qv);
}
long long query() {
return seg[1].c;
}
};
int h, w;
vector<vector<int>> arr; int r[1000005], c[1000005];
Segtree st;
int get(int i, int j) {
if (i < 0 || j < 0) return 1e9;
if (i >= h || j >= w) return 1e9;
return arr[i][j];
}
// lexicographical min of {cnt3, cnt1}
// score = cnt3 * big + cnt1
void cont(pair<int, int> i, pair<int, int> j, int d) {
if (i > j) swap(i, j);
int a1 = i.first, a2 = j.first, b1 = i.second, b2 = j.second;
vector<int> tmp({get(a1, b1), get(a1, b2), get(a2, b1), get(a2, b2)});
sort(tmp.begin(), tmp.end());
if (tmp[1] != 1e9) {
st.update(tmp[0], tmp[1] - 1, d);
} else {
st.update(tmp[0], h*w-1, d);
}
if (tmp[2] != 1e9) {
if (tmp[3] != 1e9) {
st.update(tmp[2], tmp[3] - 1, d*big);
} else {
st.update(tmp[2], h*w-1, d*big);
}
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
w = W; h = H; st = Segtree(H*W);
arr.assign(H, vector<int>(W));
for (int i = 0; i < H*W; i++) {
c[i] = C[i];
r[i] = R[i];
arr[r[i]][c[i]] = i;
}
for (int i = 0; i <= H; i++) {
for (int j = 0; j <= W; j++) {
cont({i, j}, {i - 1, j - 1}, 1);
}
}
}
int swap_seats(int a, int b) {
pair<int, int> x = {r[a], c[a]}, y = {r[b], c[b]};
cont(x, {x.first-1,x.second-1}, -1);
cont(x, {x.first-1,x.second+1}, -1);
cont(x, {x.first+1,x.second-1}, -1);
cont(x, {x.first+1,x.second+1}, -1);
cont(y, {y.first-1,y.second-1}, -1);
cont(y, {y.first-1,y.second+1}, -1);
cont(y, {y.first+1,y.second-1}, -1);
cont(y, {y.first+1,y.second+1}, -1);
swap(arr[x.first][x.second], arr[y.first][y.second]);
swap(r[a], r[b]); swap(c[a], c[b]);
cont(x, {x.first-1,x.second-1}, 1);
cont(x, {x.first-1,x.second+1}, 1);
cont(x, {x.first+1,x.second-1}, 1);
cont(x, {x.first+1,x.second+1}, 1);
cont(y, {y.first-1,y.second-1}, 1);
cont(y, {y.first-1,y.second+1}, 1);
cont(y, {y.first+1,y.second-1}, 1);
cont(y, {y.first+1,y.second+1}, 1);
return st.query();
}
