#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>
#include "seats.h"
struct SegTreeNode {
int min = 0x3f3f3f3f;
int cnt = 1;
};
static SegTreeNode get_dummy_node() {
static SegTreeNode _dummy_node = {
.min = 0x3f3f3f3f,
.cnt = 0,
};
return _dummy_node;
}
SegTreeNode combine(const SegTreeNode& a, const SegTreeNode& b) {
SegTreeNode ret = {
.min = std::min(a.min, b.min),
.cnt = (a.min == b.min) ? a.cnt + b.cnt : (a.min < b.min) ? a.cnt : b.cnt,
};
return ret;
}
int h, w;
std::vector<std::vector<int>> arr;
std::vector<int> row;
std::vector<int> column;
std::vector<SegTreeNode> tree;
std::vector<int> lazy;
void build_tree(int node, int l, int r) {
if (l == r) {
tree[node] = {
.min = 0,
.cnt = 1,
};
return;
}
int m = (l+r) >> 1;
build_tree(node<<1, l, m);
build_tree(node<<1|1, m+1, r);
tree[node] = combine(tree[node<<1], tree[node<<1|1]);
}
void push(int node, int l, int r) {
tree[node].min += lazy[node];
if (l != r) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int st, int fi, int add) {
push(node, l, r);
if (l > fi || r < st) {
return;
}
if (st <= l && r <= fi) {
lazy[node] += add;
push(node, l, r);
return;
}
int m = (l+r) >> 1;
update(node<<1, l, m, st, fi, add);
update(node<<1|1, m+1, r, st, fi, add);
tree[node] = combine(tree[node<<1], tree[node<<1|1]);
}
SegTreeNode query(int node, int l, int r, int st, int fi) {
if (l > fi || r < st) {
return get_dummy_node();
}
if (st <= l && r <= fi) {
return tree[node];
}
int m = (l+r) >> 1;
return combine(query(node<<1, l, m, st, fi), query(node<<1|1, m+1, r, st, fi));
}
void add_delta(int l, int r, int add) {
if (l < r) {
update(1, 0, h*w-1, l, r-1, add);
}
}
void activate(int x, int y, int sgn) {
int i = arr[x][y];
// 1 0
// 0 0
add_delta(i, std::min({arr[x][y+1], arr[x+1][y], arr[x+1][y+1]}), sgn);
// 0 1
// 0 0
add_delta(i, std::min({arr[x][y-1], arr[x+1][y], arr[x+1][y-1]}), sgn);
// 0 0
// 1 0
add_delta(i, std::min({arr[x-1][y], arr[x-1][y+1], arr[x][y+1]}), sgn);
// 0 0
// 0 1
add_delta(i, std::min({arr[x-1][y-1], arr[x-1][y], arr[x][y-1]}), sgn);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
arr.assign(H+2, std::vector<int>(W+2, H*W));
row.assign(H*W, 0);
column.assign(H*W, 0);
tree.resize(4*H*W+1);
lazy.assign(4*H*W+1, 0);
for (int i = 0; i < H*W; i++) {
arr[R[i]+1][C[i]+1] = i;
row[i] = R[i]+1;
column[i] = C[i]+1;
}
#if 1
build_tree(1, 0, H*W-1);
for (int i = 0; i < H*W; i++) {
int x = row[i];
int y = column[i];
activate(x, y, 1);
}
#endif
/*for (int i = 0; i < h*w; i++) {
std::cout << query(1, 0, h*w-1, i, i).min << " ";
}
std::cout << "\n";*/
}
// TODO
int swap_seats(int a, int b) {
int xa = row[a];
int ya = column[a];
int xb = row[b];
int yb = column[b];
std::set<std::pair<int,int>> distinct;
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (1 <= xa+i && xa+i <= h && 1 <= ya+j && ya+j <= w) {
distinct.emplace(xa+i, ya+j);
}
if (1 <= xb+i && xb+i <= h && 1 <= yb+j && yb+j <= w) {
distinct.emplace(xb+i, yb+j);
}
}
}
for (const auto& [x, y] : distinct) {
activate(x, y, -1);
}
std::swap(row[a], row[b]);
std::swap(column[a], column[b]);
std::swap(arr[xa][ya], arr[xb][yb]);
for (const auto& [x, y] : distinct) {
activate(x, y, 1);
}
/*for (int i = 0; i < h*w; i++) {
std::cout << query(1, 0, h*w-1, i, i).min << " ";
}
std::cout << "\n";*/
return tree[1].cnt;
}
