#include <bits/stdc++.h>
#include "seats.h"
typedef long long int64;
using namespace std;
vector<int> r,c;
const int maxn = 1e6 + 2;
int ll [maxn], rr[maxn], uu[maxn], dd[maxn], rs[maxn];
int n = 0, m = 0;
int query (int x) {
if (x == 0) return 1;
int r = 1;
for (; x >= 1; x-=x & -x) r+=rs[x];
return r;
}
void upd (int x, int d) {
for (; x < maxn; x+=x & -x) rs[x]+=d;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
r = R, c = C, n = H, m = W;
ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
for (int i = 1; i < n * m; i++){
ll[i] = min(ll[i-1], c[i]);
rr[i] = max(rr[i-1], c[i]);
uu[i] = min(uu[i-1], r[i]);
dd[i] = max(dd[i-1], r[i]);
// cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) upd(i, 1);
}
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
if (a > b) swap(a,b);
if (a == 0) ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
for (int i = max(a, 1); i <= b; i++){
if (i == 0) continue;
ll[i] = min(ll[i-1], c[i]);
rr[i] = max(rr[i-1], c[i]);
uu[i] = min(uu[i-1], r[i]);
dd[i] = max(dd[i-1], r[i]);
// cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
// if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) cout << i << " ";
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1 && query(i) - query(i - 1) != 1) upd(i, 1);
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) != i + 1 && query(i) - query(i - 1) == 1) upd(i, -1);
}
return query(maxn - 1);
}
