#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct seg {
struct node {
int iMin = 1e9, iMax = -1e9, jMin = 1e9, jMax = -1e9;
};
node op(node a, node b) {
node res;
res.iMin = min(a.iMin, b.iMin);
res.iMax = max(a.iMax, b.iMax);
res.jMin = min(a.jMin, b.jMin);
res.jMax = max(a.jMax, b.jMax);
return res;
}
vector<node> tree;
void update(int v, int rl, int rr, int pos, int i, int j) {
if (rl == rr) {
tree[v].iMax = i;
tree[v].iMin = i;
tree[v].jMax = j;
tree[v].jMin = j;
return;
}
int rm = (rl + rr)/2;
if (pos <= rm) update(v*2, rl, rm, pos, i, j);
else update(v*2+1, rm+1, rr, pos, i, j);
tree[v] = op(tree[v*2], tree[v*2+1]);
}
node query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return node();
if (rl == ql && rr == qr) return tree[v];
int rm = (rl + rr)/2;
return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
}
void init(int n, vector<pair<int, int>> ass) {
tree.resize(n*4);
for (int i = 0; i<n; i++) {
update(1, 0, n-1, i, ass[i].first, ass[i].second);
}
}
};
seg tree;
int n;
vector<pair<int, int>> seating;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
seating.resize(n);
for (int i = 0; i<n; i++) {
seating[i].first = R[i];
seating[i].second = C[i];
}
tree.init(n, seating);
}
int swap_seats(int a, int b) {
tree.update(1, 0, n-1, a, seating[b].first, seating[b].second);
tree.update(1, 0, n-1, b, seating[a].first, seating[a].second);
swap(seating[a], seating[b]);
int res = 0;
int i = 0;
while (i<n) {
// cerr << i << "\n";
auto blub = tree.query(1, 0, n-1, 0, i);
// cerr << blub.iMin << " " << blub.iMax << " " << blub.jMin << " " << blub.jMax << "\n";
// cerr << seating[i].first << " " << seating[i].second << "\n";
long long field = (long long)(blub.iMax-blub.iMin+1)*(long long)(blub.jMax-blub.jMin+1);
// cerr << i << " " << field << "\n";
assert(field>i);
if (field == i+1) {res++; i++;}
else i = field-1;
}
return res;
}
