#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
struct Data {
pair<int, int> value;
int cnt;
Data() {}
Data(pair<int, int> v, int c) : value(v), cnt(c) {}
friend Data Merge(const Data &a, const Data &b) {
if (a.value < b.value) {
return a;
} else if (a.value > b.value) {
return b;
} else {
return Data(a.value, a.cnt + b.cnt);
}
}
};
int sz;
vector<Data> tree;
vector<pair<int, int>> lazy;
void Apply(int n, int a, int b) {
tree[n].value.first += a;
tree[n].value.second += b;
lazy[n].first += a;
lazy[n].second += b;
}
void Push(int n, int lc, int rc) {
Apply(lc, lazy[n].first, lazy[n].second);
Apply(rc, lazy[n].first, lazy[n].second);
lazy[n].first = lazy[n].second = 0;
}
void Pull(int n, int lc, int rc) {
tree[n] = Merge(tree[lc], tree[rc]);
}
void Update(int n, int tl, int tr, int l, int r, int a, int b) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) return Apply(n, a, b);
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
Push(n, lc, rc);
Update(lc, tl, mid, l, r, a, b);
Update(rc, mid + 1, tr, l, r, a, b);
Pull(n, lc, rc);
}
void Build(int n, int tl, int tr) {
if (tl == tr) return void(tree[n] = Data({0, 0}, 1));
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
Build(lc, tl, mid);
Build(rc, mid + 1, tr);
Pull(n, lc, rc);
}
public:
SegmentTree() {}
SegmentTree(int n) : sz(n) {
tree.resize(2 * sz);
lazy.resize(2 * sz);
Build(1, 0, sz - 1);
}
void Update(int l, int r, int a, int b) {
return Update(1, 0, sz - 1, l, r, a, b);
}
int Query() {
return tree[1].value == make_pair(4, 0) ? tree[1].cnt : 0; // 4 squares with 1 black cell, 0 squares with 3 black cells
}
};
int H, W;
vector<int> R, C; // Rows and Columns of each student
vector<vector<int>> A; // The seating chart
SegmentTree SegTree;
int get_value(int i, int j) {
if (!(0 <= i && i < H && 0 <= j && j < W)) return H * W;
return A[i][j];
}
int square_count(int r, int c, int a) { // count black squares in 2-by-2 square, where the top left corner is (r, c)
int res = 0; // values <= a is considered a black square
if (get_value(r, c ) <= a) res++;
if (get_value(r + 1, c ) <= a) res++;
if (get_value(r, c + 1) <= a) res++;
if (get_value(r + 1, c + 1) <= a) res++;
return res;
}
void update(int r, int c, int sgn) {
vector<int> cnt(5, 0);
cnt[square_count(r - 1, c - 1, get_value(r, c) - 1)] -= sgn;
cnt[square_count(r , c - 1, get_value(r, c) - 1)] -= sgn;
cnt[square_count(r - 1, c , get_value(r, c) - 1)] -= sgn;
cnt[square_count(r , c , get_value(r, c) - 1)] -= sgn;
cnt[square_count(r - 1, c - 1, get_value(r, c))] += sgn;
cnt[square_count(r , c - 1, get_value(r, c))] += sgn;
cnt[square_count(r - 1, c , get_value(r, c))] += sgn;
cnt[square_count(r , c , get_value(r, c))] += sgn;
SegTree.Update(get_value(r, c), H * W - 1, cnt[1], cnt[3]);
}
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
H = H_, W = W_, R = R_, C = C_;
SegTree = SegmentTree(H * W);
A.assign(H, vector<int>(W, H * W));
for (int i = 0; i < H * W; i++) {
A[R[i]][C[i]] = i;
update(R[i], C[i], +1);
}
}
int swap_seats(int a, int b) {
vector<pair<int, int>> ls; // list of affected cells
for (int x = -1; x <= 1; x++) {
for (int y = -1; y <= 1; y++) {
ls.emplace_back(R[a] + x, C[a] + y);
ls.emplace_back(R[b] + x, C[b] + y);
}
}
sort(begin(ls), end(ls));
ls.resize(unique(begin(ls), end(ls)) - begin(ls));
for (auto i : ls) update(i.first, i.second, -1);
swap(R[a], R[b]), swap(C[a], C[b]);
swap(A[R[a]][C[a]], A[R[b]][C[b]]);
for (auto i : ls) update(i.first, i.second, +1);
return SegTree.Query();
}
