#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
int h, w, hw;
Vi r, c;
Vii t;
struct SegNode {
int l, r;
SegNode* left, * right;
int maxV, minV;
int GetMax(int f, int t) { // [f, t]
if (r < f || t < l) return 0;
if (f <= l && r <= t) return maxV;
return max(left->GetMax(f, t), right->GetMax(f, t));
}
int GetMin(int f, int t) { // [f, t]
if (r < f || t < l) return INT_MAX;
if (f <= l && r <= t) return minV;
return min(left->GetMin(f, t), right->GetMin(f, t));
}
void update(int t, int v) {
if (l <= t && t <= r) {
if (l == r) {
minV = maxV = v;
} else {
left->update(t, v);
right->update(t, v);
maxV = max(left->maxV, right->maxV);
minV = min(left->minV, right->minV);
}
}
}
void update(int t, SegNode* sub1, SegNode* sub2) {
if (l <= t && t <= r) {
if (l == r) {
maxV = max(sub1->maxV, sub2->maxV);
minV = min(sub1->minV, sub2->minV);
} else {
left->update(t, sub1->left, sub2->left);
right->update(t, sub1->right, sub2->right);
maxV = max(left->maxV, right->maxV);
minV = min(left->minV, right->minV);
}
}
}
SegNode(int l, int r, SegNode* sub1, SegNode* sub2) {
this->l = l; this->r = r;
if (l == r) {
maxV = max(sub1->maxV, sub2->maxV);
minV = min(sub1->minV, sub2->minV);
left = right = nullptr;
} else {
int mid = (l + r) / 2;
left = new SegNode(l, mid, sub1->left, sub2->left);
right = new SegNode(mid + 1, r, sub1->right, sub2->right);
maxV = max(left->maxV, right->maxV);
minV = min(left->minV, right->minV);
}
}
SegNode(int l, int r, const Vi& row) {
this->l = l; this->r = r;
if (l == r) {
minV = maxV = row[l];
left = right = nullptr;
} else {
int mid = (l + r) / 2;
left = new SegNode(l, mid, row);
right = new SegNode(mid + 1, r, row);
maxV = max(left->maxV, right->maxV);
minV = min(left->minV, right->minV);
}
}
};
struct SegRow {
int l, r;
SegRow* left, * right;
SegNode* rowRoot;
int GetMax(int f, int t, int yl, int yr) { // [f, t]
if (r < f || t < l) return 0;
if (f <= l && r <= t) return rowRoot->GetMax(yl, yr);
return max(left->GetMax(f, t, yl, yr), right->GetMax(f, t, yl, yr));
}
int GetMin(int f, int t, int yl, int yr) { // [f, t]
if (r < f || t < l) return INT_MAX;
if (f <= l && r <= t) return rowRoot->GetMin(yl, yr);
return min(left->GetMin(f, t, yl, yr), right->GetMin(f, t, yl, yr));
}
void update(int row, int col) {
if (l <= row && row <= r) {
if (l == r) {
rowRoot->update(col, t[row][col]);
} else {
left->update(row, col);
right->update(row, col);
rowRoot->update(col, left->rowRoot, right->rowRoot);
}
}
}
SegRow(int l, int r) {
this->l = l; this->r = r;
if (l == r) {
rowRoot = new SegNode(0, w - 1, t[l]);
left = right = nullptr;
} else {
int mid = (l + r) / 2;
left = new SegRow(l, mid);
right = new SegRow(mid + 1, r);
rowRoot = new SegNode(0, w - 1, left->rowRoot, right->rowRoot);
}
}
};
SegRow* root;
void give_initial_chart(int H, int W, Vi R, Vi C) {
h = H, w = W, hw = H * W;
r = R, c = C;
t = Vii(h, Vi(w));
forR(i, hw) {
t[R[i]][C[i]] = i;
}
root = new SegRow(0, h - 1);
}
struct Rect {
int x1, x2, y1, y2;
void expand(int x, int y) {
x1 = min(x1, x);
x2 = max(x2, x);
y1 = min(y1, y);
y2 = max(y2, y);
}
int area() {
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
vector<Rect> surroundings() {
vector<Rect> r;
if (x1 > 0) r.push_back(Rect{ 0, x1 - 1, 0, w - 1 });
if (x2 < h - 1) r.push_back(Rect{ x2 + 1, h - 1, 0, w - 1 });
if (y1 > 0) r.push_back(Rect{ 0, h - 1, 0, y1 - 1 });
if (y2 < w - 1) r.push_back(Rect{ 0, h - 1, y2 + 1, w - 1 });
return r;
}
};
int swap_seats(int a, int b) {
swap(t[r[a]][c[a]], t[r[b]][c[b]]);
swap(r[a], r[b]); swap(c[a], c[b]);
root->update(r[a], c[a]); root->update(r[b], c[b]);
#ifdef TEST_LOCAL
// test
forR(x1, h) forR(y1, w)
for (int x2 = x1; x2 < h; x2++)
for (int y2 = y1; y2 < w; y2++) {
int maxV = 0;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++) {
maxV = max(maxV, t[x][y]);
}
assert(maxV == root->GetMax(x1, x2, y1, y2));
}
#endif
int ans = 1;
Rect rect{ r[0],r[0], c[0],c[0] };
while (true) {
auto sur = rect.surroundings();
int minNext = hw;
for (auto& re : sur) {
minNext = min(minNext, root->GetMin(re.x1, re.x2, re.y1, re.y2));
}
rect.expand(r[minNext], c[minNext]);
int curMax = root->GetMax(rect.x1, rect.x2, rect.y1, rect.y2);
int curArea = rect.area();
if (curArea == curMax + 1) ans++;
if (curArea == hw) break;
}
return ans;
}
#ifdef TEST_LOCAL
int main() {
give_initial_chart(3, 3, Vi{ 0, 1, 1, 0, 0, 1, 2, 2, 2 }, Vi{ 0, 0, 1, 1, 2, 2, 0, 1, 2 });
srand(0);
forR(r, 1000000) {
swap_seats(rand() % 9, rand() % 9);
}
int r = swap_seats(0, 5);
r = swap_seats(0, 5);
return 0;
}
#endif
