#include "seats.h"
using namespace std;
const int N = 1000000, SMALL = 1000, INF = 0x3f3f3f3f;
typedef vector<int> vi;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int aa[SMALL][SMALL];
int ii[N], jj[N], ii1[N], ii2[N], jj1[N], jj2[N];
void compute_prefix(int a) {
ii1[a] = min(ii[a], a == 0 ? INF : ii1[a - 1]);
ii2[a] = max(ii[a], a == 0 ? -1 : ii2[a - 1]);
jj1[a] = min(jj[a], a == 0 ? INF : jj1[a - 1]);
jj2[a] = max(jj[a], a == 0 ? -1 : jj2[a - 1]);
}
int row[SMALL], col[SMALL];
int n, m, cnt;
void compute_row(int i) {
int j;
row[i] = INF;
for (j = 0; j < m; j++)
row[i] = min(row[i], aa[i][j]);
}
void compute_col(int j) {
int i;
col[j] = INF;
for (i = 0; i < n; i++)
col[j] = min(col[j], aa[i][j]);
}
void solve_small() {
static int ll[N], rr[N], uu[N], dd[N];
int i, iu, id, j, jl, jr;
for (i = 0; i < n; i++)
uu[i] = min(row[i], i == 0 ? INF : uu[i - 1]);
for (i = n - 1; i >= 0; i--)
dd[i] = min(row[i], i + 1 == n ? INF : dd[i + 1]);
for (j = 0; j < m; j++)
ll[j] = min(col[j], j == 0 ? INF : ll[j - 1]);
for (j = m - 1; j >= 0; j--)
rr[j] = min(col[j], j + 1 == m ? INF : rr[j + 1]);
iu = id = ii[0], jl = jr = jj[0], cnt = 1;
while (1) {
int t = INF;
if (iu > 0)
t = min(t, uu[iu - 1]);
if (id + 1 < n)
t = min(t, dd[id + 1]);
if (jl > 0)
t = min(t, ll[jl - 1]);
if (jr + 1 < m)
t = min(t, rr[jr + 1]);
if (t == INF)
break;
if (t == (id - iu + 1) * (jr - jl + 1))
cnt++;
if (iu > 0 && uu[iu - 1] == t)
iu--;
if (id + 1 < n && dd[id + 1] == t)
id++;
if (jl > 0 && ll[jl - 1] == t)
jl--;
if (jr + 1 < m && rr[jr + 1] == t)
jr++;
}
}
void give_initial_chart(int n_, int m_, vi ii_, vi jj_) {
int i, j, a;
n = n_, m = m_;
for (a = 0; a < n * m; a++) {
ii[a] = ii_[a], jj[a] = jj_[a], compute_prefix(a);
if (n <= SMALL && m <= SMALL)
aa[ii[a]][jj[a]] = a;
if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
cnt++;
}
if (n <= SMALL && m <= SMALL) {
for (i = 0; i < n; i++)
compute_row(i);
for (j = 0; j < m; j++)
compute_col(j);
}
}
int swap_seats(int l, int r) {
int a, tmp;
if (l > r)
tmp = l, l = r, r = tmp;
tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
if (n <= SMALL && m <= SMALL) {
aa[ii[l]][jj[l]] = l, aa[ii[r]][jj[r]] = r;
compute_row(ii[l]), compute_row(ii[r]), compute_col(jj[l]), compute_col(jj[r]);
solve_small();
} else {
for (a = l; a <= r; a++) {
if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
cnt--;
compute_prefix(a);
if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
cnt++;
}
}
return cnt;
}
