#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
vi r, c;
int h, w, n;
//vector<bool> checked;
map<pii, int> id;
/*vi par, sz, minR, maxR, minC, maxC;
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b){
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
sz[a] += sz[b];
minR[a] = min (minR[a], minR[b]);
minC[a] = min (minC[a], minC[b]);
maxR[a] = max (maxR[a], maxR[b]);
maxC[a] = max (maxC[a], maxC[b]);
}*/
vi minR, maxR, minC, maxC;
/*void resetDSU () {
FOR(i, 0, n-1) {
par[i] = i;
sz[i] = 1;
minR[i] = maxR[i] = r[i];
minC[i] = maxC[i] = c[i];
}
}*/
int ans = 0;
bool check (int i) {
//int p = find(i);
return (i+1) == (maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h = H;
w = W;
n = h*w;
FOR(i, 0, n-1) {
//par.pb(i);
//sz.pb(1);
minR.pb(r[i]);
maxR.pb(r[i]);
minC.pb(c[i]);
maxC.pb(c[i]);
// id[{r[i],c[i]}] = i+1;
}
FOR(i, 0, n-1) {
if (i > 0) {
maxR[i] = max (maxR[i], maxR[i-1]);
maxC[i] = max(maxC[i], maxC[i-1]);
minR[i] = min(minR[i], minR[i-1]);
minC[i] = min(minC[i], minC[i-1]);
}
ans += check(i);
}
//FOR(i, 0, n-1) checked.pb(0);
}
int swap_seats(int a, int b) {
if (a > b) swap(a,b);
FOR(i, a, b) ans -= check(i);
swap(r[a], r[b]);
swap(c[a], c[b]);
//resetDSU();
//int ret = 0;
FOR(i, a, b) {
/*FOR(dx, -1, 1) FOR(dy, -1, 1) {
int x = id[{r[i]+dx, c[i]+dy}];
x--;
if (x != -1 && x < i) unite(x, i);
}*/
//if (i > 0) unite(i, i-1);
if (i > 0) {
maxR[i] = max (r[i], maxR[i-1]);
maxC[i] = max(c[i], maxC[i-1]);
minR[i] = min(r[i], minR[i-1]);
minC[i] = min(c[i], minC[i-1]);
} else {
maxR[i] = minR[i] = r[i];
maxC[i] = minC[i] = c[i];
}
ans += check (i);
}
return ans;
}
