#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]);
}
};
int h, w;
vi rows, cols;
SegTree st;
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);
}
int swap_seats(int a, int b) {
swap(rows[a], rows[b]);
swap(cols[a], cols[b]);
st.swap_nodes(a, b);
// for (int i = 0; i < w; i++) for (int k = 0; k < w; k++) if (cols[k] == i) cout << k << " ";
// cout << "\n";
int beautiful = 0;
for (int i = 0; i < h*w;) {
Node cur = st.prefix_query(i);
// cout << "i = " << i << " (R1, R2) = (" << cur.R1 << ", " << cur.R2 << ") (C1, C2) = " << cur.C1 << ", " << cur.C2 << ") Area = " << cur.area << "\n";
if (cur.area == i+1) {
beautiful++;
// cout << "Beautiful array for: " << i << "\n";
i++;
} else {
// cout << i << " wasn't beautiful. Jumping to i = " << cur.area << "\n";
i = cur.area - 1;
}
}
return beautiful;
}
