#include "seats.h"
#include <stdlib.h>
using namespace std;
const int N = 1000000, N_ = 1 << 20, INF = 0x3f3f3f3f; // N_ = pow2(ceil(log2(N)))
typedef vector<int> vi;
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int max(int a, int b) { return a > b ? a : b; }
int max2(int a, int b, int c, int d) {
if (a < b)
return max2(b, a, c, d);
if (a < c)
return max2(c, b, a, d);
if (a < d)
return max2(d, b, c, a);
return max(max(b, c), d);
}
long long sum[N_ * 2], pref[N_ * 2]; int kk[N_ * 2], n_;
void pul(int i) {
int l = i << 1, r = l | 1;
long long 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, long long x) {
i += n_;
pref[i] = sum[i] += x;
while (i > 1)
pul(i >>= 1);
}
int **aa, ii[N], jj[N], n, m;
void give_initial_chart(int n1, int m_, vi ii_, vi jj_) {
int i, j, a;
n = n1, m = m_;
aa = (int **) malloc(n * sizeof *aa);
for (i = 0; i < n; i++)
aa[i] = (int *) malloc(m * sizeof *aa[i]);
for (a = 0; a < n * m; a++) {
ii[a] = ii_[a], jj[a] = jj_[a];
aa[ii[a]][jj[a]] = a;
}
n_ = 1;
while (n_ < n * m)
n_ <<= 1;
for (i = 0; i < n * m; i++)
sum[n_ + i] = pref[n_ + i] = 1, kk[n_ + i] = 1;
for (i = n_ - 1; i > 0; i--)
pul(i);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
if (i > 0)
update(max(aa[i - 1][j], aa[i][j]), -1);
if (j > 0)
update(max(aa[i][j - 1], aa[i][j]), -1);
if (i > 0 && j > 0) {
int a = aa[i - 1][j - 1], b = aa[i - 1][j], c = aa[i][j - 1], d = aa[i][j];
update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
}
}
}
int swap_seats(int a, int b) {
int h, i, j, i1 = ii[a], j1 = jj[a], i2 = ii[b], j2 = jj[b];
for (h = 0; h < 4; h++) {
i = i1 + di[h], j = j1 + dj[h];
if (i >= 0 && i < n && j >= 0 && j < m)
update(max(aa[i1][j1], aa[i][j]), 1);
i = i2 + di[h], j = j2 + dj[h];
if (i >= 0 && i < n && j >= 0 && j < m && (i != i1 || j != j1))
update(max(aa[i2][j2], aa[i][j]), 1);
}
for (i = max(i1 - 1, 0); i <= i1 && i + 1 < n; i++)
for (j = max(j1 - 1, 0); j <= j1 && j + 1 < m; j++) {
int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];
update(max2(a, b, c, d), -INF), update(max(max(a, b), max(c, d)), INF - 1);
}
for (i = max(i2 - 1, 0); i <= i2 && i + 1 < n; i++)
for (j = max(j2 - 1, 0); j <= j2 && j + 1 < m; j++) {
int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];
if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
update(max2(a, b, c, d), -INF), update(max(max(a, b), max(c, d)), INF - 1);
}
aa[i1][j1] = b, aa[i2][j2] = a, ii[a] = i2, jj[a] = j2, ii[b] = i1, jj[b] = j1;
for (h = 0; h < 4; h++) {
i = i1 + di[h], j = j1 + dj[h];
if (i >= 0 && i < n && j >= 0 && j < m)
update(max(aa[i1][j1], aa[i][j]), -1);
i = i2 + di[h], j = j2 + dj[h];
if (i >= 0 && i < n && j >= 0 && j < m && (i != i1 || j != j1))
update(max(aa[i2][j2], aa[i][j]), -1);
}
for (i = max(i1 - 1, 0); i <= i1 && i + 1 < n; i++)
for (j = max(j1 - 1, 0); j <= j1 && j + 1 < m; j++) {
int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];
update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
}
for (i = max(i2 - 1, 0); i <= i2 && i + 1 < n; i++)
for (j = max(j2 - 1, 0); j <= j2 && j + 1 < m; j++) {
int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];
if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
}
return kk[1];
}
