#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
namespace S4{
int n, x[N], y[N], mx[N], Mx[N], my[N], My[N], r;
void cal(int a[], int m[], int M[], int s, int e){
for(int i = s; i <= e; i++){
m[i] = min(m[i - 1], a[i]);
M[i] = max(M[i - 1], a[i]);
}
}
void ch(int s, int e, int x){
for(int i = s; i <= e; i++)
if(1LL * (Mx[i] - mx[i] + 1) * (My[i] - my[i] + 1) == i) r += x;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
for(int i = 0; i < n; i++){
x[i + 1] = R[i];
y[i + 1] = C[i];
}
mx[0] = my[0] = N;
cal(x, mx, Mx, 1, n);
cal(y, my, My, 1, n);
ch(1, n, 1);
}
int swap_seats(int a, int b){ a++; b++;
if(a > b) swap(a, b);
swap(x[a], x[b]);
swap(y[a], y[b]);
ch(a, b - 1, -1);
cal(x, mx, Mx, a, b - 1);
cal(y, my, My, a, b - 1);
ch(a, b - 1, 1);
return r;
}
}
namespace S3{
int n, x[N], y[N];
const int SZ = 1048576;
struct Seg{
int m[2*SZ], M[2*SZ];
void i(){
fill(m, m + 2*SZ, N);
fill(M, M + 2*SZ, -N);
}
void u(int x, int y){
x += SZ;
m[x] = M[x] = y;
for(x /= 2; x; x /= 2){
m[x] = min(m[2*x], m[2*x+1]);
M[x] = max(M[2*x], M[2*x+1]);
}
}
int f(int t, int k){
int x = 1;
for(; x < SZ; ){
if(t == 0 && m[2*x] <= k) x = 2*x;
if(t == 1 && M[2*x] >= k) x = 2*x;
else x = 2*x+1;
}
return x - SZ;
}
int ff(int s, int e){
return min(f(0, s - 1), f(1, e + 1));
}
} X, Y;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
X.i();
Y.i();
for(int i = 0; i < n; i++){
x[i + 1] = R[i];
y[i + 1] = C[i];
X.u(i + 1, R[i]);
Y.u(i + 1, C[i]);
}
}
int f(int sx, int ex, int sy, int ey){
int t = min(X.ff(sx, ex), Y.ff(sy, ey));
if(t > n) return 1;
return (t == (ex - sx + 1) * (ey - sy + 1) + 1) +
f(min(sx, x[t]), max(ex, x[t]), min(sy, y[t]), max(ey, y[t]));
}
int swap_seats(int a, int b){ a++; b++;
swap(x[a], x[b]);
swap(y[a], y[b]);
X.u(a, x[a]); X.u(b, x[b]);
Y.u(a, y[a]); Y.u(b, y[b]);
return f(x[1], x[1], y[1], y[1]);
}
}
int ST;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
ST = (H <= 1000 && W <= 1000 ? 3 : 4);
if(ST == 3) S3::give_initial_chart(H, W, R, C);
else S4::give_initial_chart(H, W, R, C);
}
int swap_seats(int a, int b){
if(ST == 3) return S3::swap_seats(a, b);
return S4::swap_seats(a, b);
}
