#include "seats.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 12;

int r[maxn], c[maxn];
int mxx[maxn], mnx[maxn];
int mxy[maxn], mny[maxn];
int n, m;
int ans;

bool check(int k) {
    return k == (mxx[k] - mnx[k] + 1) * (mxy[k] - mny[k] + 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H, m = W;

    mnx[0] = mny[0] = 2e9;
    for(int i = 1; i <= n * m; i++) {
        r[i] = R[i - 1] + 1;
        c[i] = C[i - 1] + 1;

        mnx[i] = min(mnx[i - 1], r[i]);
        mxx[i] = max(mxx[i - 1], r[i]);
        mny[i] = min(mny[i - 1], c[i]);
        mxy[i] = max(mxy[i - 1], c[i]);
        ans += check(i);
    }
}

int swap_seats(int a, int b) {
    a++, b++;
    if(a > b) swap(a, b);
    for(int i = a; i <= b; i++) {
        ans -= check(i);
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    for(int i = a; i <= b; i++) {
        mnx[i] = min(mnx[i - 1], r[i]);
        mxx[i] = max(mxx[i - 1], r[i]);
        mny[i] = min(mny[i - 1], c[i]);
        mxy[i] = max(mxy[i - 1], c[i]);

        ans += check(i);
    }
    return ans;
}