#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e9;
int r[N], c[N],all;
int n,m;
vector <vector <int> > a; // map ?
struct nod {
int mnf, mns, cnt;
};
nod tree[4 * N];
int lazy[2][4 * N];
nod merge(nod a, nod b) {
if (a.mnf != b.mnf) {
return (a.mnf < b.mnf ? a : b);
}
if (a.mns != b.mns) {
return (a.mns < b.mns ? a : b);
}
return {a.mnf, a.mns, a.cnt + b.cnt};
}
void build(int node, int le, int ri) {
if (le == ri) {
tree[node] = {0, 0, 1};
return ;
}
int mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void push(int node, int le, int ri) {
if (!lazy[0][node] && !lazy[1][node]) return ;
tree[node].mnf += lazy[0][node];
tree[node].mns += lazy[1][node];
if (le != ri) {
for (int ty = 0; ty < 2; ty++) {
lazy[ty][2 * node] += lazy[ty][node];
lazy[ty][2 * node + 1] += lazy[ty][node];
}
}
lazy[0][node] = lazy[1][node] = 0;
}
void update(int node, int le, int ri, int start, int end, int val, int ty) {
push(node, le, ri);
if (le > end || ri < start) return ;
if (le >= start && ri <= end) {
lazy[ty][node] = val;
push(node, le, ri);
return ;
}
int mid = (le + ri) >> 1;
update(2 * node, le, mid,start, end, val, ty);
update(2 * node + 1, mid + 1, ri, start, end, val, ty);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void upd(int l, int r, int vl, int ty) {
update(1, 1, all, l, r, vl, ty);
}
void add(int i, int j, int vl) {
vector <int> vec;
vec.pb(a[i][j]); vec.pb(a[i + 1][j]); vec.pb(a[i][j + 1]); vec.pb(a[i + 1][j + 1]);
sort(vec.begin(), vec.end());
if (vec[0] < vec[1]) upd(vec[0], vec[1] - 1, vl, 0);
if (vec[2] < vec[3]) upd(vec[2], vec[3] - 1, vl, 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H; m = W;
a = vector < vector <int> > (n + 5, vector <int> (m + 5, 0));
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
a[i][j] = n * m + 1;
}
}
all = n * m;
for (int i = 0; i < n * m; i++) {
r[i + 1] = R[i] + 1; c[i + 1] = C[i] + 1;
a[r[i + 1]][c[i + 1]] = i + 1;
}
build(1, 1, all);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// {i, j} {i + 1, j} {i, j + 1} {i + 1, j + 1}
add(i, j, 1);
}
}
}
int swap_seats(int x, int y) {
// {r[x], c[x]} --- >
x++; y++;
for (int ii = 0; ii < 2; ii++) {
int pos = (ii == 0 ? x : y);
for (int i = r[pos] - 1; i <= r[pos]; i++) {
for (int j = c[pos] - 1; j <= c[pos]; j++) {
add(i, j, -1);
}
}
}
a[r[x]][c[x]] = y;
a[r[y]][c[y]] = x;
swap(r[x], r[y]); swap(c[x], c[y]);
for (int ii = 0; ii < 2; ii++) {
int pos = (ii == 0 ? x : y);
for (int i = r[pos] - 1; i <= r[pos]; i++) {
for (int j = c[pos] - 1; j <= c[pos]; j++) {
add(i, j, 1);
}
}
}
if (tree[1].mnf == 4 && tree[1].mns == 0) {
return tree[1].cnt;
} else return 0;
}
