#pragma GCC optimize ("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
#define pii pair <ll, ll>
#define el '\n'
#define popb pop_back
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
int const N = 1e6 + 10;
int const LOG = 20;
int const inf = 1e9 + 10;
int n, m, cur;
int x[N], y[N];
struct SegTree {
int t[2][4 * N];
int getmin(int i, int tl, int tr, int l, int r) {
if(tr < l || r < tl)
return inf;
if(l <= tl && tr <= r)
return t[0][i];
int mid = (tl + tr) / 2;
return min(getmin(i + i, tl, mid, l, r), getmin(i + i + 1, mid + 1, tr, l, r));
}
int getmax(int i, int tl, int tr, int l, int r) {
if(tr < l || r < tl)
return 0;
if(l <= tl && tr <= r)
return t[1][i];
int mid = (tl + tr) / 2;
return max(getmax(i + i, tl, mid, l, r), getmax(i + i + 1, mid + 1, tr, l, r));
}
void update(int i, int tl, int tr, int pos, int val) {
if(tl == tr) {
t[0][i] = val;
t[1][i] = val;
return;
}
int mid = (tl + tr) / 2;
if(pos <= mid)
update(i + i, tl, mid, pos, val);
else
update(i + i + 1, mid + 1, tr, pos, val);
t[0][i] = min(t[0][i + i], t[0][i + i + 1]);
t[1][i] = max(t[1][i + i], t[1][i + i + 1]);
}
void build(int i, int tl, int tr, bool flag) {
if(tl == tr) {
if(flag) {
t[0][i] = x[tl];
t[1][i] = x[tl];
}
else {
t[0][i] = y[tl];
t[1][i] = y[tl];
}
return;
}
int mid = (tl + tr) / 2;
build(i + i, tl, mid, flag);
build(i + i + 1, mid + 1, tr, flag);
t[0][i] = min(t[0][i + i], t[0][i + i + 1]);
t[1][i] = max(t[1][i + i], t[1][i + i + 1]);
}
};
SegTree X, Y;
int check(int k) {
int x1 = X.getmin(1, 0, n * m - 1, 0, k);
int x2 = X.getmax(1, 0, n * m - 1, 0, k);
int y1 = Y.getmin(1, 0, n * m - 1, 0, k);
int y2 = Y.getmax(1, 0, n * m - 1, 0, k);
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H, m = W;
for(int i = 0; i < n * m; i++) {
x[i] = R[i];
y[i] = C[i];
}
X.build(1, 0, n * m - 1, 1);
Y.build(1, 0, n * m - 1, 0);
fr(i, 0, n * m - 1)
cur += (check(i) == i + 1);
}
int swap_seats(int a, int b) {
if(abs(a - b) <= n + m) {
if(a > b) swap(a, b);
fr(i, a, b - 1)
cur -= (check(i) == i + 1);
swap(x[a], x[b]);
X.update(1, 0, n * m - 1, a, x[a]);
X.update(1, 0, n * m - 1, b, x[b]);
swap(y[a], y[b]);
Y.update(1, 0, n * m - 1, a, y[a]);
Y.update(1, 0, n * m - 1, b, y[b]);
fr(i, a, b - 1)
cur += (check(i) == i + 1);
return cur;
}
swap(x[a], x[b]);
X.update(1, 0, n * m - 1, a, x[a]);
X.update(1, 0, n * m - 1, b, x[b]);
swap(y[a], y[b]);
Y.update(1, 0, n * m - 1, a, y[a]);
Y.update(1, 0, n * m - 1, b, y[b]);
int i = 0;
cur = 0;
while(i < n * m) {
int s = check(i);
if(s == i + 1) {
cur++;
i++;
}
else
i = s - 1;
}
return cur;
}
