#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, t[N*4][4], id[4] = {N, 0, N, 0}, A = 0;
vector<vector<int>> grid;
vector<array<int, 2>> pos;
vector<bool> is;
void update(int l, int r, int p, int k){
if(l == r){
t[k][0] = pos[p - 1][0];
t[k][1] = pos[p - 1][0];
t[k][2] = pos[p - 1][1];
t[k][3] = pos[p - 1][1];
return;
}
int mid = l+r>>1;
if(mid >= p)
update(l, mid, p, k<<1);
else
update(mid + 1, r, p, k<<1|1);
t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}
int get(int l, int r, int ql, int qr, int k, int s){
if(ql > r || qr < l) return id[s];
if(ql <= l && r <= qr) return t[k][s];
int mid = l+r>>1;
int al = get(l, mid, ql, qr, k<<1, s);
int ar = get(mid + 1, r, ql, qr, k<<1|1, s);
return (s % 2 ? max(al, ar) : min(al, ar));
}
int calc(){
int ans = 0;
int u = n, d = 0, l = m, r = 0;
for(int i = 0; i < n*m; ++i){
u = min(u, pos[i][0]);
d = max(d, pos[i][0]);
l = min(l, pos[i][1]);
r = max(r, pos[i][1]);
if((r - l + 1) * (d - u + 1) == i + 1){
ans++;
is[i] = 1;
}
}
return ans;
}
void calc2(int a, int b){
int u = get(1, n*m, 1, a, 1, 0);
int d = get(1, n*m, 1, a, 1, 1);
int l = get(1, n*m, 1, a, 1, 2);
int r = get(1, n*m, 1, a, 1, 3);
for(int i = a - 1; i < b - 1; ++i){
u = min(u, pos[i][0]);
d = max(d, pos[i][0]);
l = min(l, pos[i][1]);
r = max(r, pos[i][1]);
if((r - l + 1) * (d - u + 1) == i + 1){
is[i] ? 0 : A++;
is[i] = 1;
}else{
is[i] ? A-- : 0;
is[i] = 0;
}
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
n = H, m = W;
grid.resize(n, vector<int> (m, 0));
is.resize(n * m);
pos.resize(n*m);
for(int i = 0; i < n*m; ++i) grid[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
for(int i = 0; i < n*m; ++i){
update(1, n*m, i + 1, 1);
}
A = calc();
}
int swap_seats(int a, int b){
if(n <= 1000 && m <= 1000){
swap(pos[a], pos[b]);
update(1, n*m, a + 1, 1);
update(1, n*m, b + 1, 1);
calc2(a + 1, b + 1);
return A;
}
swap(pos[a], pos[b]);
grid[pos[a][0]][pos[a][1]] = a;
grid[pos[b][0]][pos[b][1]] = b;
return calc();
}
