#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int NULLV = -100;
struct Node {
int C1, C2, R1, R2, area;
Node() : C1(NULLV), C2(NULLV), R1(NULLV), R2(NULLV), area(0) {};
Node(int row, int col) : C1(col), C2(col), R1(row), R2(row), area(1) {};
Node(Node left, Node right) {
if (left.C1 == NULLV && right.C1 == NULLV) C1 = NULLV, C2 = NULLV, R1 = NULLV, R2 = NULLV, area = 0;
else if (left.C1 == NULLV) C1 = right.C1, C2 = right.C2, R1 = right.R1, R2 = right.R2, area = right.area;
else if (right.C1 == NULLV) C1 = left.C1, C2 = left.C2, R1 = left.R1, R2 = left.R2, area = left.area;
else {
C1 = min({left.C1, left.C2, right.C1, right.C2});
C2 = max({left.C1, left.C2, right.C1, right.C2});
R1 = min({left.R1, left.R2, right.R1, right.R2});
R2 = max({left.R1, left.R2, right.R1, right.R2});
area = (C2 - C1 + 1) * (R2 - R1 + 1);
}
}
};
struct SegTree {
int n; vector<Node> st;
vi rows, cols;
SegTree() : n(0) {};
SegTree(int w, int h, vi &Rows, vi &Cols) {
n = w*h;
rows = Rows;
cols = Cols;
st.assign(4*n, Node());
build(0, 0, n);
}
Node build(int i, int l, int r) {
if (l + 1 == r) return st[i] = Node(rows[l], cols[l]);
int m = l + (r - l) / 2;
return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
}
Node update(int i, int l, int r, int k, int vrow, int vcol) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = Node(vrow, vcol);
int m = l + (r - l) / 2;
return st[i] = Node(update(2*i+1, l, m, k, vrow, vcol), update(2*i+2, m, r, k, vrow, vcol));
}
Node query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return Node();
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
Node prefix_query(int r) {
return query(0, 0, n, 0, r+1);
}
void swap_nodes(int a, int b) {
swap(cols[a], cols[b]);
swap(rows[a], rows[b]);
update(0, 0, n, a, rows[a], cols[a]);
update(0, 0, n, b, rows[b], cols[b]);
}
};
struct LazySegTree {
int n; vi st, lazy;
LazySegTree() : n(0) {};
LazySegTree(int w, int h) {
n = w*h;
st.assign(4*n, 0);
lazy.assign(4*n, 0);
}
void apply(int i, int l, int r, int op) {
if (op == 0) return;
int length = r - l;
lazy[i] = op;
if (op == 1) st[i] = 0;
else st[i] = length;
}
void push_down(int i, int l, int r) {
int m = l + (r - l) / 2;
apply(2*i+1, l, m, lazy[i]);
apply(2*i+2, m, r, lazy[i]);
lazy[i] = 0;
}
int range_assign(int i, int l, int r, int ql, int qr, int v) {
if (r <= ql || qr <= l) return st[i];
if (ql <= l && r <= qr) {
apply(i, l, r, v == 0 ? 1 : 2);
return st[i];
}
push_down(i, l, r);
int m = l + (r - l) / 2;
return st[i] = range_assign(2*i+1, l, m, ql, qr, v) + range_assign(2*i+2, m, r, ql, qr, v);
}
int query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return 0;
if (ql <= l && r <= qr) return st[i];
push_down(i, l, r);
int m = l + (r - l) / 2;
return query(2*i+1, l, m, ql, qr) + query(2*i+2, m, r, ql, qr);
}
void set_zero(int l, int r) {
range_assign(0, 0, n, l, r+1, 0);
}
void set_one(int i) {
range_assign(0, 0, n, i, i+1, 1);
}
int get_beautiful() {
return query(0, 0, n, 0, n);
}
};
int ssqrt(int v) {
int s = (int) sqrt(v) - 10;
if (s <= 0) s = 1;
while (s*s < v) s++;
return s;
}
struct BlockDecomp {
int h, w;
int SX, SY;
vector<int> seg;
BlockDecomp() : h(0), w(0) {}
BlockDecomp(int H, int W)
: h(H), w(W), SX(4 * W), SY(4 * H),
seg(1LL * SX * SY, INT_MIN) {}
inline int idx(int nx, int ny) const {
return nx * SY + ny;
}
void updateY(int nx, int ny, int ly, int ry, int y, int val) {
if (ly == ry) {
seg[idx(nx, ny)] = val;
return;
}
int mid = (ly + ry) >> 1;
if (y <= mid) updateY(nx, ny << 1, ly, mid, y, val);
else updateY(nx, ny << 1 | 1, mid + 1, ry, y, val);
seg[idx(nx, ny)] =
max(seg[idx(nx, ny << 1)], seg[idx(nx, ny << 1 | 1)]);
}
void mergeY(int nx, int ny, int ly, int ry, int childL, int childR, int y) {
if (ly == ry) {
seg[idx(nx, ny)] =
max(seg[idx(childL, ny)], seg[idx(childR, ny)]);
return;
}
int mid = (ly + ry) >> 1;
if (y <= mid) mergeY(nx, ny << 1, ly, mid, childL, childR, y);
else mergeY(nx, ny << 1 | 1, mid + 1, ry, childL, childR, y);
seg[idx(nx, ny)] =
max(seg[idx(nx, ny << 1)], seg[idx(nx, ny << 1 | 1)]);
}
void updateX(int nx, int lx, int rx, int x, int y, int val) {
if (lx == rx) {
updateY(nx, 1, 0, h - 1, y, val);
return;
}
int mid = (lx + rx) >> 1;
if (x <= mid) updateX(nx << 1, lx, mid, x, y, val);
else updateX(nx << 1 | 1, mid + 1, rx, x, y, val);
mergeY(nx, 1, 0, h - 1, nx << 1, nx << 1 | 1, y);
}
void set(int x, int y, int val) { updateX(1, 0, w - 1, x, y, val); }
int queryY(int nx, int ny, int ly, int ry, int y1, int y2) const {
if (ry < y1 || y2 < ly) return INT_MIN;
if (y1 <= ly && ry <= y2) return seg[idx(nx, ny)];
int mid = (ly + ry) >> 1;
return max(queryY(nx, ny << 1, ly, mid, y1, y2),
queryY(nx, ny << 1 | 1, mid + 1, ry, y1, y2));
}
int queryX(int nx, int lx, int rx,
int x1, int x2, int y1, int y2) const {
if (rx < x1 || x2 < lx) return INT_MIN;
if (x1 <= lx && rx <= x2)
return queryY(nx, 1, 0, h - 1, y1, y2);
int mid = (lx + rx) >> 1;
return max(queryX(nx << 1, lx, mid, x1, x2, y1, y2),
queryX(nx << 1 | 1, mid + 1, rx, x1, x2, y1, y2));
}
int query(int x1, int y1, int x2, int y2) const {
return queryX(1, 0, w - 1, x1, x2, y1, y2);
}
};
int h, w;
vi rows, cols;
SegTree st;
LazySegTree prev_ans;
BlockDecomp rmq;
void give_initial_chart(int H, int W, vi R, vi C) {
h = H; w = W;
rows = R; cols = C;
st = SegTree(w, h, rows, cols);
prev_ans = LazySegTree(w, h);
rmq = BlockDecomp(H, W);
for (int i = 0; i < w*h; i++) rmq.set(cols[i], rows[i], i);
}
int queries = 0;
int swap_seats(int a, int b) {
if (a > b) swap(a, b);
queries++;
swap(rows[a], rows[b]);
swap(cols[a], cols[b]);
st.swap_nodes(a, b);
rmq.set(cols[a], rows[a], a);
rmq.set(cols[b], rows[b], b);
int start = a, end = b+1;
if (queries <= 1) start = 0, end = h*w;
prev_ans.set_zero(start, end - 1);
for (int i = start; i < end;) {
Node cur = st.prefix_query(i);
if (cur.area == i+1) {
prev_ans.set_one(i);
i++;
} else {
i = max(cur.area - 1, rmq.query(cur.C1, cur.R1, cur.C2, cur.R2));
}
}
return prev_ans.get_beautiful();
}
