Wall
A wall has n columns, each initially of height 0. Process q operations: Add(l, r, h): for each i [l, r], set height[i] (height[i], h). Remove(l, r, h): for each i [l, r], set height[i] (height[i], h). Output the final...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
A wall has $n$ columns, each initially of height 0. Process $q$ operations:
$\textbf{Add}(l, r, h)$: for each $i \in [l, r]$, set $\text{height}[i] \gets \max(\text{height}[i],\, h)$.
$\textbf{Remove}(l, r, h)$: for each $i \in [l, r]$, set $\text{height}[i] \gets \min(\text{height}[i],\, h)$.
Output the final height of each column.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Use a segment tree with lazy propagation. Each node carries a clamp interval $[\mathit{lo}, \mathit{hi}]$ meaning: any value passing through this node is clamped to $[\mathit{lo}, \mathit{hi}]$, i.e., $x \mapsto \min(\max(x, \mathit{lo}),\, \mathit{hi})$.
$\textbf{Add}(h)$: raise both bounds: $\mathit{lo} \gets \max(\mathit{lo}, h)$, $\mathit{hi} \gets \max(\mathit{hi}, h)$.
$\textbf{Remove}(h)$: lower both bounds: $\mathit{hi} \gets \min(\mathit{hi}, h)$, $\mathit{lo} \gets \min(\mathit{lo}, h)$.
Push-down composes parent and child clamps: \[ \mathit{lo}_c' = \mathrm{clamp}(\mathit{lo}_c,\, \mathit{lo}_p,\, \mathit{hi}_p), \qquad \mathit{hi}_c' = \mathrm{clamp}(\mathit{hi}_c,\, \mathit{lo}_p,\, \mathit{hi}_p), \] where $\mathrm{clamp}(x, a, b) = \min(\max(x, a), b)$.
Lemma.
The composition of two clamp intervals is again a clamp interval, so lazy propagation is well-defined. The invariant $\mathit{lo} \le \mathit{hi}$ is maintained after every Add/Remove operation.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
int lo[4 * MAXN], hi[4 * MAXN];
void init(int node, int l, int r) {
lo[node] = 0;
hi[node] = 1 << 30;
if (l == r) return;
int mid = (l + r) / 2;
init(2 * node, l, mid);
init(2 * node + 1, mid + 1, r);
}
void pushDown(int node) {
for (int child : {2 * node, 2 * node + 1}) {
lo[child] = min(max(lo[child], lo[node]), hi[node]);
hi[child] = min(max(hi[child], lo[node]), hi[node]);
}
lo[node] = 0;
hi[node] = 1 << 30;
}
void update(int node, int l, int r, int ql, int qr, int op, int h) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
if (op == 1) {
lo[node] = max(lo[node], h);
hi[node] = max(hi[node], h);
} else {
hi[node] = min(hi[node], h);
lo[node] = min(lo[node], h);
}
return;
}
pushDown(node);
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr, op, h);
update(2 * node + 1, mid + 1, r, ql, qr, op, h);
}
void query(int node, int l, int r, int ans[]) {
if (l == r) {
ans[l] = min(max(0, lo[node]), hi[node]);
return;
}
pushDown(node);
int mid = (l + r) / 2;
query(2 * node, l, mid, ans);
query(2 * node + 1, mid + 1, r, ans);
}
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
init(1, 0, n - 1);
for (int i = 0; i < k; i++)
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
query(1, 0, n - 1, finalHeight);
}Complexity Analysis
Time: $O(n + q \log n)$. Each range update is $O(\log n)$; the final traversal is $O(n)$.
Space: $O(n)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
int lo[4 * MAXN], hi[4 * MAXN];
void init(int node, int l, int r) {
lo[node] = 0;
hi[node] = 1 << 30;
if (l == r) return;
int mid = (l + r) / 2;
init(2 * node, l, mid);
init(2 * node + 1, mid + 1, r);
}
void pushDown(int node) {
for (int child : {2 * node, 2 * node + 1}) {
// Compose: clamp child's [lo,hi] by parent's [lo,hi]
lo[child] = min(max(lo[child], lo[node]), hi[node]);
hi[child] = min(max(hi[child], lo[node]), hi[node]);
}
lo[node] = 0;
hi[node] = 1 << 30;
}
// op=1: add (clamp_low), op=2: remove (clamp_high)
void update(int node, int l, int r, int ql, int qr, int op, int h) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
if (op == 1) {
// clamp_low(h): raise lo and hi if needed
lo[node] = max(lo[node], h);
hi[node] = max(hi[node], h);
} else {
// clamp_high(h): lower hi and lo if needed
hi[node] = min(hi[node], h);
lo[node] = min(lo[node], h);
}
return;
}
pushDown(node);
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr, op, h);
update(2 * node + 1, mid + 1, r, ql, qr, op, h);
}
void query(int node, int l, int r, int ans[]) {
if (l == r) {
// The final value is 0 clamped by [lo, hi]
ans[l] = min(max(0, lo[node]), hi[node]);
return;
}
pushDown(node);
int mid = (l + r) / 2;
query(2 * node, l, mid, ans);
query(2 * node + 1, mid + 1, r, ans);
}
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
init(1, 0, n - 1);
for (int i = 0; i < k; i++) {
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
query(1, 0, n - 1, finalHeight);
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
vector<int> op(k), left(k), right(k), height(k);
for (int i = 0; i < k; i++) {
scanf("%d %d %d %d", &op[i], &left[i], &right[i], &height[i]);
}
vector<int> ans(n);
buildWall(n, k, op.data(), left.data(), right.data(),
height.data(), ans.data());
for (int i = 0; i < n; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.