#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1003;
int n, m;
vector<vector<int>> a;
int seg[N + N][N << 1];
void upd (int nd, int l, int r, int p, int v, int ver) {
if (l == r) {
seg[ver][nd] = v;
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v, ver);
} else {
upd(rs, mid + 1, r, p, v, ver);
}
seg[ver][nd] = max(seg[ver][nd + 1], seg[ver][rs]);
}
int qry (int nd, int l, int r, int s, int e, int ver) {
if (l >= s && r <= e) {
return seg[ver][nd];
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
return qry(nd + 1, l, mid, s, e, ver);
} else {
if (mid < s) {
return qry(rs, mid + 1, r, s, e, ver);
} else {
return max(qry(nd + 1, l, mid, s, e, ver), qry(rs, mid + 1, r, s, e, ver));
}
}
}
int getver (int x, bool col) {
return x + n * col;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int Dfs (int mx, int mxr, int mnr, int mxc, int mnc) {
//cout << mx << ' ' << mxr << ' ' << mnr << ' ' << mxc << ' ' << mnc << '\n';
int ret = 0;
if ((mxr - mnr + 1) * (mxc - mnc + 1) == mx + 1) {
ret++;
}
vector<int> nmxx(4, 1e9);
if (mxr + 1 < n) {
int nmx = max(mx, qry(0, 0, m - 1, mnc, mxc, getver(mxr + 1, false)));
nmxx[0] = nmx;
}
if (mnr - 1 >= 0) {
int nmx = max(mx, qry(0, 0, m - 1, mnc, mxc, getver(mnr - 1, false)));
nmxx[1] = nmx;
}
if (mxc + 1 < m) {
int nmx = max(mx, qry(0, 0, n - 1, mnr, mxr, getver(mxc + 1, true)));
nmxx[2] = nmx;
}
if (mnc - 1 >= 0) {
int nmx = max(mx, qry(0, 0, n - 1, mnr, mxr, getver(mnc - 1, true)));
nmxx[3] = nmx;
}
int mn = *min_element(nmxx.begin(), nmxx.end());
if (nmxx[0] == mn && mn < 1e9) {
ret += Dfs(mn, mxr + 1, mnr, mxc, mnc);
} else if (nmxx[1] == mn && mn < 1e9) {
ret += Dfs(mn, mxr, mnr - 1, mxc, mnc);
} else if (nmxx[2] == mn && mn < 1e9) {
ret += Dfs(mn, mxr, mnr, mxc + 1, mnc);
} else if (nmxx[3] == mn && mn < 1e9) {
ret += Dfs(mn, mxr, mnr, mxc, mnc - 1);
}
return ret;
}
vector<int> r, c;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H, m = W;
r = R; c = C;
a.resize(n);
for (int i = 0; i < n; ++i) {
a[i].resize(m);
}
for (int i = 0; i < n * m; ++i) {
a[r[i]][c[i]] = i;
upd(0, 0, m - 1, c[i], i, getver(r[i], false));
upd(0, 0, n - 1, r[i], i, getver(c[i], true));
}
}
int swap_seats(int x, int y) {
upd(0, 0, m - 1, c[y], x, getver(r[y], false));
upd(0, 0, n - 1, r[y], x, getver(c[y], true));
upd(0, 0, m - 1, c[x], y, getver(r[x], false));
upd(0, 0, n - 1, r[x], y, getver(c[x], true));
swap(c[x], c[y]);
swap(r[x], r[y]);
return Dfs(0, r[0], r[0], c[0], c[0]);
}
