#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld long double
#define ll long long
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define lb lower_bound
#define ub upper_bound
const int N = 1e6 + 10, inf = 1e9;
struct segTree {
struct node {
int maxX, minX, maxY, minY;
};
vector<node> tree;
int size;
void init(int n) {
size = 1;
while(size < n) {
size *= 2;
}
tree.assign(2 * size - 1, {-inf, inf, -inf, inf});
}
node combine(node a, node b) {
a.maxX = max(a.maxX, b.maxX);
a.maxY = max(a.maxY, b.maxY);
a.minX = min(a.minX, b.minX);
a.minY = min(a.minY, b.minY);
return a;
}
void upd(int u, int X, int Y, int x, int lx, int rx) {
if(rx - lx == 1) {
tree[x] = {X, X, Y, Y};
return;
}
int m = (lx + rx) / 2;
if(u < m) {
upd(u, X, Y, 2 * x + 1, lx, m);
}else {
upd(u, X, Y, 2 * x + 2, m, rx);
}
tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
}
void upd(int u, int X, int Y) {
upd(u, X, Y, 0, 0, size);
}
node qry (int l, int r, int x, int lx, int rx) {
if(l >= rx || lx >= r) {
return {-inf, inf, -inf, inf};
}
if(lx >= l && r >= rx) {
return tree[x];
}
int m = (rx + lx) / 2;
node s1 = qry(l, r, 2 * x + 1, lx, m);
node s2 = qry(l, r, 2 * x + 2, m, rx);
return combine(s1, s2);
}
node qry(int l, int r) {
return qry(l, r, 0, 0, size);
}
};
int n, h, w, r[N], c[N], ans[N], answ;
segTree x;
int getSum(int x1, int y1, int x2, int y2) {
return x2 * y2 - (x1 - 1) * y2 - x2 * (y1 - 1) + (x1 - 1) * (y1 - 1);
}
int swap_seats(int a, int b) {
if(abs(a - b) && max(h ,w) > 1000) {
if(a > b) {
swap(a, b);
} a++, b++;
swap(r[a], r[b]);
swap(c[a], c[b]);
x.upd(a, r[a], c[a]);
x.upd(b, r[b], c[b]);
auto an = x.qry(0, a + 1);
int minX, maxX, minY, maxY;
minX = an.minX, maxX = an.maxX;
minY = an.minY, maxY = an.maxY;
for(int i = a; i <= b; i++) {
minX = min(minX, r[i]);
maxX = max(maxX, r[i]);
//
minY = min(minY, c[i]);
maxY = max(maxY, c[i]);
int sum = getSum(minX, minY, maxX, maxY);
if(sum == i && !ans[i]) {
ans[i] = 1;
answ++;
} else if(sum != i) {
if(ans[i] == 1) {
ans[i] = 0;
answ--;
}
}
}
return answ;
} else {
int i = 1; answ = 0;
while(i <= n) {
auto an = x.qry(0, i + 1);
int minX, maxX, minY, maxY;
//
minX = an.minX, maxX = an.maxX;
minY = an.minY, maxY = an.maxY;
int sum = getSum(minX, minY, maxX, maxY);
if(sum == i) {
answ++;
} else {
i = sum - 1;
}
}
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = sz(R), h = H, w = W;
x.init(n + 2);
int minX, maxX, minY, maxY;
for(int i = 0; i < n; i++) {
r[i + 1] = R[i];
c[i + 1] = C[i];
x.upd(i + 1, R[i], C[i]);
if(i == 0) {
answ++, ans[i + 1] = 1;
minX = maxX = R[i];
minY = maxY = C[i];
} else {
//
minX = min(minX, R[i]);
maxX = max(maxX, R[i]);
//
minY = min(minY, C[i]);
maxY = max(maxY, C[i]);
if(getSum(minX, minY, maxX, maxY) == (i + 1)) {
ans[i + 1] = 1;
answ++;
}
}
}
}
