#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int N, H, W;
vector<int> R, C;
vector<vector<int>> seats;
vector<vector<int>> is_valid; //avoid double counting when updating
vector<int> updates_list;
vector<pair<int, int>> updates_pending;
inline void ADD(pair<int, int> &a, pair<int, int> b) {
a.first += b.first;
a.second += b.second;
}
/* a subset is rectangle if there are only 4 2*2 grid with 1 black squares and 0 2*2 grid woth 3 black squares */
struct segment_tree { /* number of 2*2 gird with 1 black square is always >= 4, so we can use segment tree and count minimum (4) */
vector<pair<int, int>> tree, lazy;
vector<int> cnt;
inline void init(int &n) {
tree.assign(4 * n, {0, 0}); //minimums element
lazy.assign(4 * n, {0, 0}); //lazy propagation
cnt.assign(4 * n, 0); //number of minimum
build(1, 0, n - 1);
}
inline void pull(int &n) {
tree[n] = min(tree[n * 2], tree[(n * 2) + 1]);
cnt[n] = 0;
if (tree[n] == tree[n * 2]) cnt[n] += cnt[n * 2];
if (tree[n] == tree[(n * 2) + 1]) cnt[n] += cnt[(n * 2) + 1];
}
inline void push(int &n) {
ADD(tree[n * 2], lazy[n]);
ADD(tree[n * 2 + 1], lazy[n]);
ADD(lazy[n * 2], lazy[n]);
ADD(lazy[n * 2 + 1], lazy[n]);
lazy[n] = {0, 0};
}
void build(int n, int tl, int tr) {
if (tl == tr) {
cnt[n] = 1;
} else {
int mid = (tl + tr) / 2;
build(n * 2, tl, mid);
build(n * 2 + 1, mid + 1, tr);
pull(n);
}
}
void upd(int n, int tl, int tr, int le, int ri, pair<int, int> x) {
if (ri < tl || tr < le || tl > tr) return;
if (le <= tl && tr <= ri) {
ADD(tree[n], x);
ADD(lazy[n], x);
return;
}
int mid = (tl + tr) / 2;
push(n);
upd(n * 2, tl, mid, le, ri, x);
upd(n * 2 + 1, mid + 1, tr, le, ri, x);
pull(n);
}
inline int query() {
return (tree[1] == make_pair(4, 0))? cnt[1] : 0;
}
} solver;
void update() {
sort(updates_list.begin(), updates_list.end());
updates_list.resize(unique(updates_list.begin(), updates_list.end()) - updates_list.begin());
pair<int, int> cur_update = {0, 0};
for (int i = 0; i < updates_list.size() - 1; i++) {
ADD(cur_update, updates_pending[updates_list[i]]);
solver.upd(1, 0, N - 1, updates_list[i], updates_list[i + 1] - 1, cur_update);
}
for (auto &i : updates_list) updates_pending[i] = {0, 0};
updates_list.clear();
}
void push_update(int i, int j, int val) {
if (is_valid[i][j] == 0 && val == -1) return;
if (is_valid[i][j] == 1 && val == +1) return;
is_valid[i][j] ^= 1;
pair<int, int> grids[4];
grids[0] = make_pair(seats[i][j], 0); //top left
grids[1] = make_pair(seats[i][j + 1], 1); //top right
grids[2] = make_pair(seats[i + 1][j + 1], 2); //bottom right
grids[3] = make_pair(seats[i + 1][j], 3); //bottom left
sort(grids, grids + 4);
for (int k = 0; k < 3; k++) {
int start = grids[k].first;
int end = grids[k + 1].first;
pair<int, int> updates = {0, 0};
if (start >= end) {
continue;
} else if (k == 0) {
updates = {val, 0};
} else if (k == 1) {
if ((grids[0].second ^ grids[1].second) == 2) { //diagonal black squares, mark that it's no longer a rectangle
updates = {2 * val, 0}; //by assigning impossibility (minimum wil be >= 5, so no longer valid)
} else {
continue; //nothing changes
}
} else if (k == 2) {
updates = {0, val}; //3 black squares
}
ADD(updates_pending[start], updates);
ADD(updates_pending[end], {-updates.first, -updates.second});
updates_list.emplace_back(start);
updates_list.emplace_back(end);
}
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
H = h, W = w;
N = H * W;
R = r, C = c;
seats.assign(H + 2, vector<int>(W + 2, N));
is_valid.assign(H + 2, vector<int>(W + 2, 0));
updates_pending.resize(N + 2, {0, 0});
for (int i = 0; i < N; i++) seats[R[i] + 1][C[i] + 1] = i;
for (int i = 0; i <= H; i++) {
for (int j = 0; j <= W; j++) {
push_update(i, j, +1);
}
}
solver.init(N);
update();
}
int swap_seats(int a, int b) {
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
push_update(R[a] + i, C[a] + j, -1);
push_update(R[b] + i, C[b] + j, -1);
}
}
swap(R[a], R[b]); swap(C[a], C[b]);
swap(seats[R[a] + 1][C[a] + 1], seats[R[b] + 1][C[b] + 1]);
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
push_update(R[a] + i, C[a] + j, +1);
push_update(R[b] + i, C[b] + j, +1);
}
}
update();
return solver.query();
}
