#include "seats.h"
#include <vector>
#include <algorithm>
using namespace std;
int N_total;
vector<int> pos; // Stores the position of seat i
vector<int> val; // The value (time) at grid position i
int tree_min[4000005];
int tree_cnt[4000005];
int lazy[4000005];
// --- Segment Tree Functions ---
void push_up(int v) {
tree_min[v] = min(tree_min[2 * v], tree_min[2 * v + 1]);
tree_cnt[v] = 0;
if (tree_min[v] == tree_min[2 * v]) tree_cnt[v] += tree_cnt[2 * v];
if (tree_min[v] == tree_min[2 * v + 1]) tree_cnt[v] += tree_cnt[2 * v + 1];
}
void apply(int v, int add) {
tree_min[v] += add;
lazy[v] += add;
}
void push_down(int v) {
if (lazy[v] != 0) {
apply(2 * v, lazy[v]);
apply(2 * v + 1, lazy[v]);
lazy[v] = 0;
}
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree_min[v] = 0;
tree_cnt[v] = 1;
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
push_up(v);
}
}
void update(int v, int tl, int tr, int l, int r, int add) {
if (l > r) return;
if (l == tl && r == tr) {
apply(v, add);
} else {
push_down(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(r, tm), add);
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
push_up(v);
}
}
// --- Logic for 1D Transitions ---
// A transition exists between pos i and i+1 for all k in [min_time, max_time - 1]
void update_transition(int i, int factor) {
int t1 = val[i];
int t2 = val[i + 1];
if (t1 > t2) swap(t1, t2);
// Transition exists when one is black and one is white: time is in [t1, t2-1]
update(1, 0, N_total - 1, t1, t2 - 1, factor);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
// Assuming H=1 for Subtask 5. If W=1, the logic is identical.
N_total = H * W;
pos.resize(N_total);
val.assign(N_total + 2, N_total); // Padding with "infinity" time
for (int i = 0; i < N_total; i++) {
// Since it's 1D, we care about the position in the row/column
int p = (H == 1) ? C[i] : R[i];
pos[i] = p + 1; // 1-based to allow for padding at index 0
val[p + 1] = i;
}
build(1, 0, N_total - 1);
// Initial transitions (including boundaries)
for (int i = 0; i <= N_total; i++) {
update_transition(i, 1);
}
}
int swap_seats(int a, int b) {
int p1 = pos[a];
int p2 = pos[b];
// Identify affected adjacent pairs
vector<int> affected = {p1 - 1, p1, p2 - 1, p2};
sort(affected.begin(), affected.end());
affected.erase(unique(affected.begin(), affected.end()), affected.end());
// 1. Remove old transition counts
for (int p : affected) update_transition(p, -1);
// 2. Swap
swap(val[p1], val[p2]);
swap(pos[a], pos[b]);
// 3. Add new transition counts
for (int p : affected) update_transition(p, 1);
// The condition for a 1D rectangle is exactly 2 transitions
if (tree_min[1] == 2) return tree_cnt[1];
return 0;
}
