#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 value, maxX, minX, maxY, minY, lazy;
};
vector<node> tree;
int size;
void init(int n) {
size = 1;
while(size < n) {
size *= 2;
}
tree.assign(2 * size - 1, {0, -inf, inf, -inf, inf, -1});
}
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);
a.value += b.value;
a.lazy = -1;
return a;
}
void shift(int x, int lx, int rx) {
if(rx - lx == 1 || tree[x].lazy == -1) {
tree[x].lazy = -1;
return;
}
int mid = (lx + rx) / 2;
tree[2 * x + 1].lazy = tree[x].lazy;
tree[2 * x + 1].value = tree[x].lazy * (mid - lx);
tree[2 * x + 2].lazy = tree[x].lazy;
tree[2 * x + 2].value = tree[x].lazy * (rx - mid);
tree[x].lazy = -1;
}
void upd_interval(int l, int r, int v, int x, int lx, int rx) {
shift(x, lx, rx);
if(lx >= r || rx <= l) {
return;
}
if(lx >= l && rx <= r) {
tree[x].value = v;
tree[x].lazy = v;
shift(x, lx, rx);
return;
}
int mid = (lx + rx) / 2;
upd_interval(l, r, v, 2 * x + 1, lx, mid);
upd_interval(l, r, v, 2 * x + 2, mid, rx);
tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
}
void upd_interval(int l, int r, int v) {
upd_interval(l, r, v, 0, 0, size);
}
void upd(int u, int X, int Y, int v, int x, int lx, int rx) {
shift(x, lx, rx);
if(rx - lx == 1) {
if(X != -1) {
tree[x].maxX = tree[x].minX = X;
tree[x].maxY = tree[x].minY = Y;
}
if(v != -1) {
tree[x].value = v;
}
return;
}
int m = (lx + rx) / 2;
if(u < m) {
upd(u, X, Y, v, 2 * x + 1, lx, m);
}else {
upd(u, X, Y, v, 2 * x + 2, m, rx);
}
tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
}
void upd(int u, int X, int Y, int v) {
upd(u, X, Y, v, 0, 0, size);
}
node qry (int l, int r, int x, int lx, int rx) {
shift(x, lx, rx);
if(l >= rx || lx >= r) {
return {0, -inf, inf, -inf, inf, -1};
}
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) {
bool flag = false;
if(max(h, w) <= 1000) {
flag = true;
}
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], -1);
x.upd(b, r[b], c[b], -1);
auto an = x.qry(0, a);
int minX, maxX, minY, maxY;
minX = an.minX, maxX = an.maxX;
minY = an.minY, maxY = an.maxY;
if(!flag) {
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--;
}
}
}
} else {
// cout << 1 << endl;
answ -= x.qry(a, b + 1).value;
x.upd_interval(a, b + 1, 0);
for(int i = a; i <= b; i++) {
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) {
x.upd(i, -1, -1, 1);
answ++;
} else if(sum > i) {
i = sum - 1;
}
}
}
return answ;
}
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], -1);
if(i == 0) {
answ++, ans[i + 1] = 1;
x.upd(i + 1, -1, -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)) {
x.upd(i + 1, -1, -1, 1);
ans[i + 1] = 1;
answ++;
}
}
}
}
