#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
#define f first
#define s second
#define pii pair<int,int>
#define Pii pair<pair<int,int>, int>
#define mp make_pair
vector<vector<int> > a, f;
int n,h, w, T;
Pii tree[4 * N];
int dx[] = {0, 0, 0, -1, 1};
int dy[] = {0, -1, 1, 0, 0};
pair<int,int> lazy[4 * N], pos[N];
void add(pii &a, pii b) {
a.f += b.f;
a.s += b.s;
}
void push(int u,int l,int r) {
add(tree[u].f, lazy[u]);
if(l != r) {
add(lazy[2 * u],lazy[u]);
add(lazy[2 * u + 1], lazy[u]);
}
lazy[u] = {0, 0};
}
void upd(int u, int st, int en, int l,int r, pii v) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u] = v;
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, v); upd(2 * u + 1, st, en, mid + 1, r, v);
if(tree[2 * u].f != tree[2 * u + 1].f) tree[u] = min(tree[2 * u], tree[2 * u + 1]);
else tree[u].f = tree[2 * u + 1].f, tree[u].s = tree[2 * u + 1].s + tree[2 * u].s;
}
void build(int u, int l,int r) {
tree[u].s = r - l + 1;
if(l == r) return;
build(2 * u, l, (l + r) / 2); build(2 * u + 1, (l + r)/2 + 1, r);
}
void add(int i, int j, int t) {
if(i > h || j > w || i <= 0 || j <= 0 || f[i][j] == T) return;
f[i][j] = T;
int m = max(max(a[i + 1][j], a[i - 1][j]), max(a[i][j + 1], a[i][j - 1]));
m = max(a[i - 1][j], a[i][j + 1]); upd(1, m ,a[i][j] - 1, 1, n, mp(0, t));
m = max(a[i + 1][j], a[i][j + 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
m = max(a[i - 1][j], a[i][j - 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
m = max(a[i - 1][j], a[i][j + 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
m = min(a[i - 1][j], a[i][j + 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
m = min(a[i + 1][j], a[i][j + 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
m = min(a[i - 1][j], a[i][j - 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
m = min(a[i - 1][j], a[i][j + 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H * W; h = H, w = W;
a.resize(H + 2, vector<int> (W + 2)); f.resize(H + 2, vector<int> (W + 2));
build(1, 1, n);
for(int i = 0; i <= H; i++) {
a[i][0] = a[i][W + 1] = n + 1;
}
for(int i = 0; i <= W; i++) {
a[0][i] = a[H + 1][i] = n + 1;
}
for(int i = 0; i < H * W; i++) {
++R[i]; ++C[i];
a[R[i]][C[i]] = i + 1;
pos[i + 1] = {R[i], C[i]};
}
++T;
for(int i = 1; i <= H; i++) {
for(int j = 1; j <= W; j++) {
add(i, j, 1);
}
}
}
int swap_seats(int c, int b) {
++c; ++b;
++T;
for(int k = 0; k < 5; k++) {
add(pos[c].f + dx[k], pos[c].s + dy[k], -1);
add(pos[b].f + dx[k], pos[b].s + dy[k], -1);
}
swap(a[pos[b].f][pos[b].s], a[pos[c].f][pos[c].s]);
swap(pos[c], pos[b]);
pair<pair<int,int>, int> p = tree[1];
++T;
for(int k = 0; k < 5; k++) {
add(pos[c].f + dx[k], pos[c].s + dy[k], 1);
add(pos[b].f + dx[k], pos[b].s + dy[k], 1);
}
p = tree[1];
assert(p.f.f >= 4);
if(p.f.s != 0 || p.f.f != 4) return 0;
return p.s;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}*/
