#include "seats.h"
#include <iostream>
#include <climits>
using namespace std;
#define pb push_back
#define S second
#define F first
typedef pair<int, int> pii;
const int N = 1e6 + 200;
const int inf = (1 << 30);
int S, ans = 0;
int H, W;
pii pos[N];
int rx[N], lx[N], ry[N], ly[N];
struct tree {
pii t[N << 2];
int SZ;
void upd(int v, int val) {
v = v + SZ - 1;
t[v] = {val, val};
if (val == inf)
t[v].F *= -1;
v >>= 1;
while (v) {
t[v].F = max(t[v * 2].F, t[v * 2 + 1].F);
t[v].S = min(t[v * 2].S, t[v * 2 + 1].S);
v >>= 1;
}
}
pii get(int l, int r) {
l = l + SZ - 1;
r = r + SZ - 1;
pii ans = {-inf, +inf};
while (true) {
if (l % 2 == 1) {
ans.F = max(ans.F, t[l].F);
ans.S = min(ans.S, t[l].S);
}
if (r % 2 == 0) {
ans.F = max(ans.F, t[r].F);
ans.S = min(ans.S, t[r].S);
}
if (l == r)
break;
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
return ans;
}
} tx, ty;
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
H = _H, W = _W;
S = H * W;
swap(R, C);
for (int i = 0; i < H * W; ++i)
pos[i + 1] = {R[i] + 1, C[i] + 1};
if (H + W <= 2000) {
tx.SZ = 1;
while (tx.SZ < S)
tx.SZ <<= 1;
ty.SZ = tx.SZ;
for (int i = 1; i <= tx.SZ; ++i) {
if (i > S) {
tx.upd(i, +inf);
ty.upd(i, +inf);
}
else {
tx.upd(i, pos[i].F);
ty.upd(i, pos[i].S);
}
}
}
return;
rx[0] = -inf, lx[0] = +inf;
ry[0] = -inf, ly[0] = +inf;
for (int i = 1; i <= S; ++i) {
rx[i] = max(rx[i - 1], pos[i].F);
lx[i] = min(lx[i - 1], pos[i].F);
ry[i] = max(ry[i - 1], pos[i].S);
ly[i] = min(ly[i - 1], pos[i].S);
if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
ans++;
}
return;
}
int get(int pos) {
pair<int, int> a = tx.get(1, pos);
pair<int, int> b = ty.get(1, pos);
return (a.F - a.S + 1) * (b.F - b.S + 1);
}
int swap_seats(int a, int b) {
++a, ++b;
if (a > b)
swap(a, b);
swap(pos[a], pos[b]);
if (H + W <= 2000) {
tx.upd(a, pos[a].F);
tx.upd(b, pos[b].F);
ty.upd(a, pos[a].S);
ty.upd(b, pos[b].S);
int pos = 1, cnt = 0;
while (true) {
int npos = get(pos);
if (npos == pos) {
cnt++;
}
pos = npos + (pos == npos);
if (pos > S) break;
}
return cnt;
}
for (int i = a; i <= b; ++i) {
if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
ans--;
rx[i] = max(rx[i - 1], pos[i].F);
lx[i] = min(lx[i - 1], pos[i].F);
ry[i] = max(ry[i - 1], pos[i].S);
ly[i] = min(ly[i - 1], pos[i].S);
if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
ans++;
}
return ans;
}
