#include "seats.h"
using namespace std;
const int N = 1000000, N_ = 1 << 20, SMALL = 1000, INF = 0x3f3f3f3f; // N_ = pow2(ceil(log2(N)))
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], aa_[N];
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++;
}
}
int sum[N_ * 2], pref[N_ * 2], kk[N_ * 2], n_;
void pul(int i) {
int l = i << 1, r = l | 1, x, y;
sum[i] = sum[l] + sum[r];
x = pref[l], y = sum[l] + pref[r];
if (x < y)
pref[i] = x, kk[i] = kk[l];
else if (x > y)
pref[i] = y, kk[i] = kk[r];
else
pref[i] = x, kk[i] = kk[l] + kk[r];
}
void update(int i, int x) {
i += n_;
pref[i] = sum[i] += x;
while (i > 1)
pul(i >>= 1);
}
void give_initial_chart(int n1, int m_, vi ii_, vi jj_) {
int i, j, a;
n = n1, m = m_;
for (a = 0; a < n * m; a++) {
ii[a] = ii_[a], jj[a] = jj_[a], compute_prefix(a);
if (n == 1)
aa_[jj[a]] = a;
else 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 == 1) {
n_ = 1;
while (n_ < m)
n_ <<= 1;
for (i = 0; i < n_; i++)
if (i < m)
sum[n_ + i] = pref[n_ + i] = 1, kk[n_ + i] = 1;
for (i = n_ - 1; i > 0; i--)
pul(i);
for (i = 1; i < m; i++)
update(max(aa_[i - 1], aa_[i]), -1);
} else 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;
if (n == 1) {
int i = jj[l], j = jj[r];
if (i + 1 == j) {
if (i > 0)
update(max(aa_[i - 1], aa_[i]), 1);
update(max(aa_[i], aa_[i + 1]), 1);
if (i + 2 < m)
update(max(aa_[i + 1], aa_[i + 2]), 1);
} else if (j + 1 == i) {
if (j > 0)
update(max(aa_[j - 1], aa_[j]), 1);
update(max(aa_[j], aa_[j + 1]), 1);
if (j + 2 < m)
update(max(aa_[j + 1], aa_[j + 2]), 1);
} else {
if (i > 0)
update(max(aa_[i - 1], aa_[i]), 1);
if (i + 1 < m)
update(max(aa_[i], aa_[i + 1]), 1);
if (j > 0)
update(max(aa_[j - 1], aa_[j]), 1);
if (j + 1 < m)
update(max(aa_[j], aa_[j + 1]), 1);
}
aa_[i] = r, aa_[j] = l;
if (i + 1 == j) {
if (i > 0)
update(max(aa_[i - 1], aa_[i]), -1);
update(max(aa_[i], aa_[i + 1]), -1);
if (i + 2 < m)
update(max(aa_[i + 1], aa_[i + 2]), -1);
} else if (j + 1 == i) {
if (j > 0)
update(max(aa_[j - 1], aa_[j]), -1);
update(max(aa_[j], aa_[j + 1]), -1);
if (j + 2 < m)
update(max(aa_[j + 1], aa_[j + 2]), -1);
} else {
if (i > 0)
update(max(aa_[i - 1], aa_[i]), -1);
if (i + 1 < m)
update(max(aa_[i], aa_[i + 1]), -1);
if (j > 0)
update(max(aa_[j - 1], aa_[j]), -1);
if (j + 1 < m)
update(max(aa_[j], aa_[j + 1]), -1);
}
tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
cnt = kk[1];
} else if (n <= SMALL && m <= SMALL) {
tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
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 {
tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
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;
}
