#pragma GCC optimize("O3")
#include "seats.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 1e3 + 5;
int tree[3 * MAXN][3 * MAXN];
int arr[MAXN][MAXN];
pair<int,int> pos[MAXN * MAXN];
int h = 0, w = 0;
array<int, 4> tree1d[3 * MAXN * MAXN];
void build(int l, int r, int k) {
if (l == r) {
tree1d[k][0] = pos[l].fi;
tree1d[k][1] = pos[l].se;
tree1d[k][2] = pos[r].fi;
tree1d[k][3] = pos[r].se;
return;
}
int m = (l + r) / 2;
build(m + 1, r, k * 2 + 1);
build(l, m, k * 2);
tree1d[k][0] = min(tree1d[k * 2][0], tree1d[k * 2 + 1][0]);
tree1d[k][1] = min(tree1d[k * 2][1], tree1d[k * 2 + 1][1]);
tree1d[k][2] = max(tree1d[k * 2][2], tree1d[k * 2 + 1][2]);
tree1d[k][3] = max(tree1d[k * 2][3], tree1d[k * 2 + 1][3]);
}
array<int,4> qry(int l, int r, int k, int a) {
if (r < 0 || a < l) {
array<int,4> ret;
ret[0] = INF;
ret[1] = INF;
ret[2] = -1;
ret[3] = -1;
return ret;
}
if (0 <= l && r <= a)
return tree1d[k];
int m = (l + r) / 2;
array<int,4> x = qry(l, m, k * 2, a);
array<int,4> y = qry(m + 1, r, k * 2 + 1, a);
x[0] = min(x[0], y[0]);
x[1] = min(x[1], y[1]);
x[2] = max(x[2], y[2]);
x[3] = max(x[3], y[3]);
return x;
}
void upd(int l, int r, int k, int a) {
if (r < a || a < l)
return;
if (a <= l && r <= a) {
tree1d[k][0] = pos[l].fi;
tree1d[k][1] = pos[l].se;
tree1d[k][2] = pos[r].fi;
tree1d[k][3] = pos[r].se;
return;
}
int m = (l + r) / 2;
if (m >= a)
upd(l, m, k * 2, a);
if (m + 1 >= a)
upd(m + 1, r, k * 2 + 1, a);
tree1d[k][0] = min(tree1d[k * 2][0], tree1d[k * 2 + 1][0]);
tree1d[k][1] = min(tree1d[k * 2][1], tree1d[k * 2 + 1][1]);
tree1d[k][2] = max(tree1d[k * 2][2], tree1d[k * 2 + 1][2]);
tree1d[k][3] = max(tree1d[k * 2][3], tree1d[k * 2 + 1][3]);
}
void prop(int l, int r, int k, int ind) {
if (l == r) {
tree[ind][k] = max(tree[ind * 2][k], tree[ind * 2 + 1][k]);
return;
}
int m = (l + r) / 2;
prop(l, m, k * 2, ind);
prop(m + 1, r, k * 2 + 1, ind);
tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}
void prop(int l, int r, int k, int ind, int x) {
if (r < x || x < l)
return;
if (x <= l && r <= x) {
tree[ind][k] = max(tree[ind * 2][k], tree[ind * 2 + 1][k]);
return;
}
int m = (l + r) / 2;
prop(l, m, k * 2, ind, x);
prop(m + 1, r, k * 2 + 1, ind, x);
tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}
void build1(int l, int r, int k, int k2, int ind) {
if (l == r) {
tree[k2][k] = arr[ind][l];
return;
}
int m = (l + r) / 2;
build1(l, m, k * 2, k2, ind);
build1(m + 1, r, k * 2 + 1, k2, ind);
tree[k2][k] = max(tree[k2][k * 2], tree[k2][k * 2 + 1]);
}
void build2(int l, int r, int k) {
if (l == r) {
build1(0, w - 1, 1, k, l);
return;
}
int m = (l + r) / 2;
build2(l, m, k * 2);
build2(m + 1, r, k * 2 + 1);
prop(0, w - 1, 1, k);
}
int qry1(int l, int r, int k, int ind, int c, int d) {
if (r < c || d < l)
return 0;
if (c <= l && r <= d)
return tree[ind][k];
int m = (l + r) / 2;
return max(qry1(l, m, k * 2, ind, c, d), qry1(m + 1, r, k * 2 + 1, ind, c, d));
}
int qry2(int l, int r, int k, int a, int b, int c, int d) {
if (r < a || b < l)
return 0;
if (a <= l && r <= b)
return qry1(0, w - 1, 1, k, c, d);
int m = (l + r) / 2;
return max(qry2(l, m, k * 2, a, b, c, d), qry2(m + 1, r, k * 2 + 1, a, b, c, d));
}
void upd1(int l, int r, int k, int ind, int x, int val) {
if (r < x || x < l)
return;
if (x <= l && r <= x) {
tree[ind][k] = val;
return;
}
int m = (l + r) / 2;
if (m >= x)
upd1(l, m, k * 2, ind, x, val);
if (m + 1 <= x)
upd1(m + 1, r, k * 2 + 1, ind, x, val);
tree[ind][k] = max(tree[ind][k * 2], tree[ind][k * 2 + 1]);
}
void upd2(int l, int r, int k, int x, int y, int val) {
if (r < x || x < l)
return;
if (x <= l && r <= x) {
upd1(0, w - 1, 1, k, y, val);
return;
}
int m = (l + r) / 2;
if (m >= x)
upd2(l, m, k * 2, x, y, val);
if (m + 1 <= x)
upd2(m + 1, r, k * 2 + 1, x, y, val);
prop(0, w - 1, 1, k, y);
}
int ret = 0;
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
h = H, w = W;
for (int i = 0; i < h * w; i++) {
arr[r[i]][c[i]] = i;
pos[i] = {r[i], c[i]};
}
build(0, h * w - 1, 1);
build2(0, h - 1, 1);
int x1, y1, x2, y2;
tie(x1, y1) = pos[0];
tie(x2, y2) = pos[0];
for (int i = 0; i < h * w; i++) {
x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
array<int,4> z = qry(0, h * w - 1, 1, val);
x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
i = val;
if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
ret++;
}
}
int swap_seats(int a, int b) {
int cnt = 0;
int x1, y1, x2, y2;
array<int,4> z = qry(0, h * w - 1, 1, a);
x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
for (int i = a; i <= b; i++) {
x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
if (val > b)
break;
z = qry(0, h * w - 1, 1, val);
x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
i = val;
if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
cnt--;
}
upd2(0, h - 1, 1, pos[a].fi, pos[a].se, b);
upd2(0, h - 1, 1, pos[b].fi, pos[b].se, a);
swap(pos[a], pos[b]);
upd(0, h * w - 1, 1, a);
upd(0, h * w - 1, 1, b);
z = qry(0, h * w - 1, 1, a);
x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
for (int i = a; i <= b; i++) {
x1 = min(x1, pos[i].fi); y1 = min(y1, pos[i].se);
x2 = max(x2, pos[i].fi); y2 = max(y2, pos[i].se);
int val = qry2(0, h - 1, 1, x1, x2, y1, y2);
if (val > b)
break;
z = qry(0, h * w - 1, 1, val);
x1 = z[0], y1 = z[1], x2 = z[2], y2 = z[3];
i = val;
if ((y2 - y1 + 1) * (x2 - x1 + 1) == val + 1)
cnt++;
}
ret += cnt;
return ret;
}
