#include "seats.h"
#include <bits/stdc++.h>
#define maxn 1000005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int h, w; vector<int> r, c;
struct node {
int val1 = 0, val2 = 0, cnt = 1;
node() {}
node(int _val1, int _val2, int _cnt) : val1(_val1), val2(_val2), cnt(_cnt) {}
node operator + (const node &other) const {
if (val1 == other.val1 && val2 == other.val2) return node(val1, val2, cnt+other.cnt);
if (val1 == other.val1) return val2 < other.val2 ? *this : other;
return val1 < other.val1 ? *this : other;
}
bool operator == (const node &other) const {
return val1 == other.val1 && val2 == other.val2;
}
} st[4*maxn];
int lz1[4*maxn], lz2[4*maxn];
void down(int r) {
if (lz1[r]) {
int &d = lz1[r];
st[r<<1].val1 += d;
st[r<<1|1].val1 += d;
lz1[r<<1] += d;
lz1[r<<1|1] += d;
d = 0;
}
if (lz2[r]) {
int &d = lz2[r];
st[r<<1].val2 += d;
st[r<<1|1].val2 += d;
lz2[r<<1] += d;
lz2[r<<1|1] += d;
d = 0;
}
}
vector<vector<int> > matrix;
void update1(int u, int v, int d, int r = 1, int lo = 0, int hi = h*w-1) {
if (u <= lo && hi <= v) {
st[r].val1 += d; lz1[r] += d;
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update1(u, v, d, r<<1, lo, mid);
if (v > mid) update1(u, v, d, r<<1|1, mid+1, hi);
st[r] = st[r<<1] + st[r<<1|1];
}
void update2(int u, int v, int d, int r = 1, int lo = 0, int hi = h*w-1) {
if (u <= lo && hi <= v) {
st[r].val2 += d; lz2[r] += d;
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update2(u, v, d, r<<1, lo, mid);
if (v > mid) update2(u, v, d, r<<1|1, mid+1, hi);
st[r] = st[r<<1] + st[r<<1|1];
}
void try_case_one(const vector<int> &block, int mult) {
int min1 = INT_MAX, min2 = INT_MAX; for (int i : block)
if (min1 > i) {
min2 = min1;
min1 = i;
} else if (min2 > i) min2 = i;
if (min1 < min2) update1(min1, min2-1, mult);
}
void try_case_two(const vector<int> &block, int mult) {
int max1 = 0, max2 = 0; for (int i : block)
if (max1 < i) {
max2 = max1;
max1 = i;
} else if (max2 < i) max2 = i;
if (max2 < max1) update2(max2, max1-1, mult);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
r = R; c = C;
for (int i = 0; i < H*W; i++) {
++r[i]; ++c[i];
}
matrix.assign(h+2, vector<int>(w+2, h*w));
for (int i = 0; i < H*W; i++) matrix[r[i]][c[i]] = i;
for (int i = 0; i <= h; i++)
for (int j = 0; j <= w; j++) {
try_case_one({matrix[i][j], matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1]}, 1);
try_case_two({matrix[i][j], matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1]}, 1);
}
}
int swap_seats(int a, int b) {
vector<ii > nho;
nho.emplace_back(r[a]-1, c[a]-1);
nho.emplace_back(r[a], c[a]-1);
nho.emplace_back(r[a]-1, c[a]);
nho.emplace_back(r[a], c[a]);
nho.emplace_back(r[b]-1, c[b]-1);
nho.emplace_back(r[b], c[b]-1);
nho.emplace_back(r[b]-1, c[b]);
nho.emplace_back(r[b], c[b]);
sort(nho.begin(), nho.end());
nho.erase(unique(nho.begin(), nho.end()), nho.end());
for (auto [u, v] : nho) {
try_case_one({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, -1);
try_case_two({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, -1);
}
swap(matrix[r[a]][c[a]], matrix[r[b]][c[b]]);
swap(r[a], r[b]); swap(c[a], c[b]);
for (auto [u, v] : nho) {
try_case_one({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, 1);
try_case_two({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, 1);
}
assert(st[1].val1 == 4 && st[1].val2 == 0);
return st[1].cnt;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
3 4
*/
