#include "seats.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair<int, int> pii;
const int LOG = 20;
const int N = 1 << LOG;
const int OO = 2e9;
int n, m, X[N], Y[N];
vector<vector<int>> mat;
int t[2 * N], c[2 * N], p[2 * N];
void propagate(int u) {
t[2 * u] += p[u];
t[2 * u + 1] += p[u];
p[2 * u] += p[u];
p[2 * u + 1] += p[u];
p[u] = 0;
}
pii merge(pii a, pii b) {
pii c;
c.X = min(a.X, b.X);
c.Y = (a.X == c.X ? a.Y : 0) + (b.X == c.X ? b.Y : 0);
return c;
}
void update(int l, int r, int w, int u = 1, int lo = 0, int hi = N) {
if(r <= lo || hi <= l) { return; }
if(l <= lo && hi <= r) {
t[u] += w;
p[u] += w;
return;
}
int mi = (lo + hi) / 2;
propagate(u);
update(l, r, w, 2 * u, lo, mi);
update(l, r, w, 2 * u + 1, mi, hi);
pii res = merge({t[2 * u], c[2 * u]}, {t[2 * u + 1], c[2 * u + 1]});
t[u] = res.X;
c[u] = res.Y;
}
pii query(int l, int r, int u = 1, int lo = 0, int hi = N) {
if(r <= lo || hi <= l) { return {OO, 0}; }
if(l <= lo && hi <= r) {
return {t[u], c[u]};
}
int mi = (lo + hi) / 2;
propagate(u);
return merge(query(l, r, 2 * u, lo, mi), query(l, r, 2 * u + 1, mi, hi));
}
void add(int x, int y, int w) {
vector<int> v;
for(int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j) {
v.PB(mat[x + i][y + j]);
}
}
sort(v.begin(), v.end());
update(v[0], v[1], w);
update(v[2], v[3], 10 * w);
}
void give_initial_chart(int nn, int mm, vector<int> XX, vector<int> YY) {
for(int i = 2 * N - 1; i > 0; --i) {
c[i] = 1;
if(i < N) { c[i] = c[2 * i] + c[2 * i + 1]; }
}
n = nn;
m = mm;
mat.resize(n + 2);
for(int i = 0; i <= n + 1; ++i) {
mat[i].resize(m + 2, n * m + 1);
}
for(int i = 1; i <= n * m; ++i) {
X[i] = XX[i - 1] + 1;
Y[i] = YY[i - 1] + 1;
mat[X[i]][Y[i]] = i;
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) {
add(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
++a; ++b;
for(int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j) {
add(X[a] - i, Y[a] - j, -1);
add(X[b] - i, Y[b] - j, -1);
}
}
swap(mat[X[a]][Y[a]], mat[X[b]][Y[b]]);
swap(X[a], X[b]);
swap(Y[a], Y[b]);
for(int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j) {
add(X[a] - i, Y[a] - j, 1);
add(X[b] - i, Y[b] - j, 1);
}
}
return query(1, n * m + 1).Y;
}
