#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 2000000
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
class SegmentTree {
private:
struct Node {
int minVal;
int count;
int lazy;
Node(int minVal = numeric_limits<int>::max(), int count = 0, int lazy = 0)
: minVal(minVal), count(count), lazy(lazy) {}
};
vector<Node> tree;
int size;
void apply(int pos, int delta) {
tree[pos].minVal += delta;
tree[pos].lazy += delta;
}
void push(int pos) {
apply(2 * pos, tree[pos].lazy);
apply(2 * pos + 1, tree[pos].lazy);
tree[pos].lazy = 0;
}
void pull(int pos) {
if (tree[2 * pos].minVal < tree[2 * pos + 1].minVal) {
tree[pos].minVal = tree[2 * pos].minVal;
tree[pos].count = tree[2 * pos].count;
} else if (tree[2 * pos].minVal > tree[2 * pos + 1].minVal) {
tree[pos].minVal = tree[2 * pos + 1].minVal;
tree[pos].count = tree[2 * pos + 1].count;
} else {
tree[pos].minVal = tree[2 * pos].minVal;
tree[pos].count = tree[2 * pos].count + tree[2 * pos + 1].count;
}
}
public:
SegmentTree(const vector<int>& arr) {
size = arr.size();
tree.resize(2 * size);
for (int i = 1; i <= size; ++i) {
tree[size + i - 1] = Node(arr[i - 1], 1);
}
for (int i = size - 1; i > 0; --i) {
pull(i);
}
}
void rangeAdd(int l, int r, int delta) {
if( l > r ) return;
l += size - 1;
r += size - 1;
int l0 = l, r0 = r;
while (l <= r) {
if (l % 2 == 1) apply(l++, delta);
if (r % 2 == 0) apply(r--, delta);
l /= 2;
r /= 2;
}
for (int i : {l0 / 2, r0 / 2}) {
while (i > 0) {
push(i);
pull(i);
i /= 2;
}
}
}
pair<int, int> query() {
push(1); // Ensure root is up-to-date
return {tree[1].minVal, tree[1].count};
}
};
SegmentTree st(vi(MAXN));
vvi arr;
vvb seen;
int n, H, W;
void add(int x, int y, int t) {
vi v = {arr[x][y], arr[x + 1][y], arr[x][y + 1], arr[x + 1][y + 1]};
sort(v.begin(), v.end());
st.rangeAdd( v[0], min(n, v[1] - 1), t);
st.rangeAdd( v[2], min(n, v[3] - 1), t);
}
vi R, C;
void give_initial_chart(int h, int w, vi r, vi c) {
R = r;
C = c;
H = h;
W = w;
n = H * W;
st.rangeAdd(n+1, MAXN, INF);
arr.resize(H + 2, vi(W + 2, 0));
seen.resize(H + 2, vb(W + 2, false));
for (int i = 0; i < n; i++) arr[R[i] + 1][C[i] + 1] = i + 1;
for (int i = 0; i <= W + 1; i++) arr[0][i] = arr[H + 1][i] = INF;
for (int i = 0; i <= H + 1; i++) arr[i][0] = arr[i][W + 1] = INF;
for (int i = 0; i <= H; i++)
for (int j = 0; j <= W; j++)
add(i, j, 1);
}
int swap_seats(int a, int b) {
vp cur = {
{R[a] + 1, C[a] + 1}, {R[a], C[a] + 1}, {R[a] + 1, C[a]},
{R[a], C[a]}, {R[b] + 1, C[b] + 1}, {R[b] + 1, C[b]},
{R[b], C[b] + 1}, {R[b], C[b]}
};
for (auto &[x, y] : cur) {
if (!seen[x][y]) add(x, y, -1);
seen[x][y] = true;
}
for (auto &[x, y] : cur) seen[x][y] = false;
swap(arr[R[a] + 1][C[a] + 1], arr[R[b] + 1][C[b] + 1]);
swap(R[a], R[b]);
swap(C[a], C[b]);
for (auto &[x, y] : cur) {
if (!seen[x][y]) add(x, y, 1);
seen[x][y] = true;
}
for (auto &[x, y] : cur) seen[x][y] = false;
return st.query().S;
}
// signed main(){
// give_initial_chart(1,5,{0, 0, 0, 0, 0},{0, 1, 2, 3, 4});
// cout<<swap_seats(0,1)<<'\n';
// cout<<swap_seats(0,3)<<'\n';
// cout<<swap_seats(4,0)<<'\n';
// }
