#include "bits/stdc++.h"
#include "seats.h"
using namespace std;
struct node_max {
int seg_st, seg_en, seg_mid;
int val;
node_max *left, *right;
node_max(int st, int en) {
seg_st = st;
seg_en = en;
int mi = (st + en) / 2;
seg_mid = mi;
val = 0;
if (st == en) return;
left = new node_max(st, mi);
right = new node_max(mi+1, en);
}
void update(int pos, int to) {
if (pos > seg_en || pos < seg_st) {
return;
}
if (seg_st == seg_en) {
val = to;
return;
}
left->update(pos, to);
right->update(pos, to);
val = max(left->val, right->val);
}
int query(int a, int b) {
if (a > seg_en) return INT_MIN;
if (b < seg_st) return INT_MIN;
if (a <= seg_st && b >= seg_en) {
return val;
}
return max(left->query(a, b), right->query(a, b));
}
} *hmax, *vmax;
struct node_min {
int seg_st, seg_en, seg_mid;
int val;
node_min *left, *right;
node_min(int st, int en) {
seg_st = st;
seg_en = en;
int mi = (st + en) / 2;
seg_mid = mi;
val = 0;
if (st == en) return;
left = new node_min(st, mi);
right = new node_min(mi+1, en);
}
void update(int pos, int to) {
if (pos > seg_en || pos < seg_st) {
return;
}
if (seg_st == seg_en) {
val = to;
return;
}
left->update(pos, to);
right->update(pos, to);
val = min(left->val, right->val);
}
int query(int a, int b) {
if (a > seg_en) return INT_MAX;
if (b < seg_st) return INT_MAX;
if (a <= seg_st && b >= seg_en) {
return val;
}
return min(left->query(a, b), right->query(a, b));
}
} *hmin, *vmin;
const int MXN = 1000005;
int h, w, n;
int hat[MXN], vat[MXN];
bool work[MXN];
int counter = 0;
void valid(int c) {
int hmi = hmin->query(0, c);
int hma = hmax->query(0, c);
int vmi = vmin->query(0, c);
int vma = vmax->query(0, c);
bool ans = (((vma - vmi + 1) * (hma - hmi + 1)) == (c + 1));
if (ans == work[c]) return;
if (work[c]) {
work[c] = ans;
counter--;
}
else {
work[c] = ans;
counter++;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
n = (h * w);
// rows
hmax = new node_max(0, n-1);
hmin = new node_min(0, n-1);
// cols
vmax = new node_max(0, n-1);
vmin = new node_min(0, n-1);
for (int i=0; i<n; i++) {
int r = R[i];
int c = C[i];
hmax->update(i, r);
hmin->update(i, r);
vmax->update(i, c);
vmin->update(i, c);
hat[i] = r;
vat[i] = c;
}
memset(work, 0, sizeof work);
for (int i=0; i<n; i++) {
valid(i);
}
}
int swap_seats(int a, int b) {
int ax = hat[a];
int ay = vat[a];
int bx = hat[b];
int by = vat[b];
hmax->update(a, bx);
hmin->update(a, bx);
vmax->update(a, by);
vmin->update(a, by);
hmax->update(b, ax);
hmin->update(b, ax);
vmax->update(b, ay);
vmin->update(b, ay);
for (int i=a; i<=b; i++) {
valid(i);
}
return counter;
}
