#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;
else 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 == 1LL * (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]);
}
}
namespace S5{
int n, x[N], c[N];
const int SZ = 1048576;
struct Seg{
int d[2*SZ], l[2*SZ], c[2*SZ];
void spr(int x){
d[2*x] += l[x];
l[2*x] += l[x];
d[2*x+1] += l[x];
l[2*x+1] += l[x];
l[x] = 0;
}
void mrg(int x){
d[x] = max(d[2*x], d[2*x+1]);
c[x] = 0;
if(d[x] == d[2*x]) c[x] += c[2*x];
if(d[x] == d[2*x+1]) c[x] += c[2*x+1];
}
void i(int n){
for(int i = SZ; i < SZ + n; i++){
d[i] = SZ - i;
c[i] = 1;
}
for(int i = SZ - 1; i; i--) mrg(i);
}
void u(int s, int e, int v, int x = 1, int p = 1, int q = SZ){
if(e < p || q < s) return;
if(s <= p && q <= e){
d[x] += v;
l[x] += v;
return;
}
spr(x);
u(s, e, v, 2*x, p, p+q>>1);
u(s, e, v, 2*x+1, p+q+2>>1, q);
mrg(x);
}
} S;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = W;
S.i(n);
for(int i = 0; i < n; i++){
x[i + 1] = C[i] + 1;
c[C[i] + 1] = i + 1;
}
for(int i = 1; i < n; i++) S.u(max(c[i], c[i + 1]), n, 1);
}
void ch(int x, int v){
if(x > 1) S.u(max(c[x - 1], c[x]), n, -1);
if(x < n) S.u(max(c[x], c[x + 1]), n, -1);
c[x] = v;
if(x > 1) S.u(max(c[x - 1], c[x]), n, 1);
if(x < n) S.u(max(c[x], c[x + 1]), n, 1);
}
int swap_seats(int a, int b){ a++; b++;
swap(x[a], x[b]);
ch(x[a], a);
ch(x[b], b);
return S.c[1];
}
}
int ST;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
ST = (H == 1 ? 5 : H <= 1000 && W <= 1000 ? 3 : 4);
if(ST == 3) S3::give_initial_chart(H, W, R, C);
else if(ST == 4) S4::give_initial_chart(H, W, R, C);
else S5::give_initial_chart(H, W, R, C);
}
int swap_seats(int a, int b){
if(ST == 3) return S3::swap_seats(a, b);
if(ST == 4) return S4::swap_seats(a, b);
return S5::swap_seats(a, b);
}
