#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int N = 1e6 + 5, INF = 1e9 + 5;
int n;
struct SegTree{
pair<int, int> tree[N * 4];
pair<int, int> merge(pair<int, int> a, pair<int, int> b){
return {min(a.first, b.first), max(a.second, b.second)};
}
void build(vector<int> &arr, int v = 1, int l = 0, int r = n - 1){
if(l == r) tree[v] = {arr[l], arr[l]};
else{
int m = l + (r - l) / 2;
build(arr, v * 2, l, m);
build(arr, v * 2 + 1, m + 1, r);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
pair<int, int> query(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return {INF, -INF};
else if(l == tl && r == tr) return tree[v];
else{
int tm = tl + (tr - tl) / 2;
return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
}
}
void update(int pos, int val, int v = 1, int l = 0, int r = n - 1){
if(l == r) tree[v] = {val, val};
else{
int m = l + (r - l) / 2;
if(pos <= m) update(pos, val, v * 2, l, m);
else update(pos, val, v * 2 + 1, m + 1, r);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
};
SegTree sgtx, sgty;
vector<int> X, Y;
void give_initial_chart(int H, int W, vector<int> X_, vector<int> Y_) {
X = X_, Y = Y_;
n = H * W;
sgtx.build(X);
sgty.build(Y);
}
int swap_seats(int a, int b){
sgtx.update(a, X[b]);
sgty.update(a, Y[b]);
sgtx.update(b, X[a]);
sgty.update(b, Y[a]);
swap(X[a], X[b]);
swap(Y[a], Y[b]);
pair<int, int> x, y;
int cur = 0, ans = 0;
while(cur < n){
x = sgtx.query(0, cur);
y = sgty.query(0, cur);
if((x.second - x.first + 1) * (y.second - y.first + 1) == cur + 1) ans++, cur++;
else cur = (x.second - x.first + 1) * (y.second - y.first + 1) - 1;
}
return ans;
}
