#include "bits/stdc++.h"
#include "seats.h"
using namespace std;
struct node_co {
int seg_st, seg_en, seg_mid;
int valmax, valmin;
node_co *left, *right;
node_co(int st, int en) {
seg_st = st;
seg_en = en;
int mi = (st + en) / 2;
seg_mid = mi;
valmax = valmin = 0;
if (st == en) return;
left = new node_co(st, mi);
right = new node_co(mi+1, en);
}
void update(int pos, int to) {
if (pos > seg_en || pos < seg_st) {
return;
}
if (seg_st == seg_en) {
valmax = to;
valmin = to;
return;
}
left->update(pos, to);
right->update(pos, to);
valmax = max(left->valmax, right->valmax);
valmin = min(left->valmin, right->valmin);
}
pair<int, int> query(int a, int b) {
if (a > seg_en || b < seg_st) return make_pair(INT_MIN, INT_MAX);
if (a <= seg_st && b >= seg_en) {
return make_pair(valmax, valmin);
}
pair<int, int> le = left->query(a, b);
pair<int, int> ri = right->query(a, b);
return make_pair(max(le.first, ri.first), min(le.second, ri.second));
}
} *hno, *vno;
const int MXN = 1000005;
int h, w, n;
int hat[MXN], vat[MXN];
bool work[MXN];
int counter = 0;
void valid(int c) {
pair<int, int> h = hno->query(0, c);
pair<int, int> v = vno->query(0, c);
int hdif = h.first - h.second + 1;
int vdif = v.first - v.second + 1;
bool ans = false;
if (c + 1 == (hdif * vdif)) {
ans = true;
}
// cout << " > " << c << ' ' << ans << ' ' << h.first << ' ' << h.second << ' ' << v.first << ' ' << v.second << endl;
if (ans == work[c]) return;
if (ans) counter++;
else counter--;
work[c] = ans;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
n = (h * w);
hno = new node_co(0, n-1);
vno = new node_co(0, n-1);
for (int i=0; i<n; i++) {
hat[i] = R[i];
vat[i] = C[i];
// cout << i << ' ' << R[i] << ' ' << C[i] << endl;
hno->update(i, R[i]);
vno->update(i, C[i]);
}
memset(work, 0, sizeof work);
counter = 0;
for (int i=0; i<n; i++) {
valid(i);
}
}
int swap_seats(int a, int b) {
int ax = hat[a], ay = vat[a];
int bx = hat[b], by = vat[b];
hat[b] = ax, vat[b] = ay;
hat[a] = bx, vat[a] = by;
hno->update(a, hat[a]);
hno->update(b, hat[b]);
vno->update(a, vat[a]);
vno->update(b, vat[b]);
for (int i=min(a, b); i<=max(a, b); i++) {
valid(i);
}
return counter;
}
