#include "seats.h"
using namespace std;
const int S = 1000000, 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 ii[S], jj[S], ii1[S], ii2[S], jj1[S], jj2[S];
void compute(int h) {
ii1[h] = min(ii[h], h == 0 ? INF : ii1[h - 1]);
ii2[h] = max(ii[h], h == 0 ? -1 : ii2[h - 1]);
jj1[h] = min(jj[h], h == 0 ? INF : jj1[h - 1]);
jj2[h] = max(jj[h], h == 0 ? -1 : jj2[h - 1]);
}
int cnt;
void give_initial_chart(int n, int m, vi ii_, vi jj_) {
int h;
for (h = 0; h < n * m; h++) {
ii[h] = ii_[h], jj[h] = jj_[h], compute(h);
cnt += (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
}
}
int swap_seats(int l, int r) {
int h, 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;
for (h = l; h <= r; h++) {
cnt -= (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
compute(h);
cnt += (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
}
return cnt;
}
