Core Logic and Mathematical Principles
The Scanning Line algorithm is a key application of segment trees in two-dimensional geometric computations. The classic problem is: given $N$ rectangles aligned with the coordinate axes in a Cartesian plane, compute their area union or perimeter union.
1. Spatial Slicing and Dimensional Reduction
Directly solving the area union of two-dimensional shapes involves handling extremely complex boundary intersection scenarios. The core idea of the scanning line algorithm is dimensional reduction and divide-and-conquer: a vertical line (the scanning line) moves from left to right (or a line perpendicular to the $y$-axis moves from bottom to top).
The left and right vertical edges of the rectangles are abstracted as event points on the scanning line:
- Left edge (entry edge): The start of the rectangle region, marked with $+1$.
- Right edge (exit edge): The end of the rectangle region, marked with $-1$.
If all left and right edges of the rectangles are sorted in ascending order of their $x$ coordinates, the entire two-dimensional plane is divided into $2N-1$ vertical non-intersecting strips. For the $i^{th}$ strip, its width is $\Delta x = x_{i+1} - x_i$, and its height $H$ is the length union of all valid vertical segments intercepted by the current scanning line. Thus, the area of the strip is:
$$ \Delta S = \Delta x \times H $$
The final total area is the algebraic sum of the areas of all strips: $S_{all} = \sum \Delta S$.
2. Discretization and Interval Continuity Mapping
Since the range of the vertical coordinate $y$ is often vast (e.g., $10^9$) or consists of real numbers, it cannot be directly used as an array index in the segment tree. All vertical coordinates $y$ of the rectangles must be extracted, deduplicated, sorted in ascending order, and mapped to a discretized array $raw\text{ }y$ of size $M$.
Critical Point: The nodes of the segment tree maintain intervals (length of segments), not points. If there are $M$ unique $y$ values after discretization, they will form $M-1$ basic segments. If a leaf node $u$ of the segment tree represents the closed interval $[l, r]$, its actual vertical interval in geometric terms is $[raw\text{ }y[l], raw\text{ }y[r+1]]$. Therefore, the root node of the segment tree maintains the interval $[1, M-1]$.
State Design and Algorithm Derivation
1. Design of Scanning Line Event Structure
Each rectangle contributes two vertical segments, defined as ScanLine:
x: The horizontal coordinate of the segment (used for sorting to trigger the scanning).y1,y2: The vertical coordinate interval of the segment (satisfying $y1 < y2$).mark: Entry edge is $1$, exit edge is $-1$.
2. Design of Segment Tree Node States
Unlike basic segment trees, the standard scanning line does not require the introduction of a standard pushdown lazy marking mechanism due to its special symmetric add-and-subtract property (entry edge $+1$, exit edge $-1$). Each node $u$ maintains two core states:
cover[u]: The number of times the current interval is completely covered (ifcover[u] > 0, it indicates that the geometric interval represented by this node is fully activated).len[u]: The actual geometric segment length covered in the current interval.
3. Specialized pushup Control Logic
Since there is no pushdown, the correctness of a node's data is entirely determined by its own cover and the len of its child nodes. When executing update(u, l, r, ql, qr, val) causes a change in cover[u], the len[u] is immediately recalculated through a specialized pushup:
$$ len[u] = \begin{cases} raw\text{ }y[r+1] - raw\text{ }y[l], & \text{if } cover[u] > 0 \ len[u \ll 1] + len[u \ll 1 | 1], & \text{if } cover[u] = 0 \text{ and } l < r \ 0, & \text{if } cover[u] = 0 \text{ and } l = r \end{cases} $$
- Logical Explanation: If the current node
cover > 0, it indicates that the interval is fully covered, and its geometric span is directly calculated; ifcover == 0and it is not a leaf node, its geometric length is determined by the sum reported by the left and right child nodes; if it is a leaf node andcover == 0, the length is $0$.
C++ Standard Source Code (NOIP Style)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int MAXN = 200005; // 2 rectangles contribute 4 edges, space must be allocated to 2 * N times 4
struct ScanLine {
long long x;
long long y1, y2;
int mark;
// Strictly sort in ascending order by x coordinate, process entry edges first (higher mark) to prevent boundary discontinuity
bool operator<(const ScanLine& b) const {
if (x != b.x) return x < b.x;
return mark > b.mark;
}
} line[MAXN << 1];
long long raw_y[MAXN << 1];
long long len[MAXN << 3]; // Critical pitfall: due to doubling of points, segment tree space must be MAXN * 8
int cover[MAXN << 3];
// Specialized unmarked pushup mechanism
inline void pushup(int u, int l, int r) {
if (cover[u] > 0) {
len[u] = raw_y[r + 1] - raw_y[l]; // Map to geometric physical interval
} else if (l == r) {
len[u] = 0; // Leaf node and not covered
} else {
len[u] = len[u << 1] + len[u << 1 | 1];
}
}
// Core geometric interval update: the incoming ql, qr must be the indices of the discretized array
void update(int u, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
cover[u] += val;
pushup(u, l, r); // Coverage state changed, immediately calculate the actual length of the current node
return;
}
int m = (l + r) >> 1;
if (ql <= m) update(u << 1, l, m, ql, qr, val);
if (qr > m) update(u << 1 | 1, m + 1, r, ql, qr, val);
pushup(u, l, r);
}
int main() {
int n = read();
int cnt = 0;
for (int i = 1; i <= n; ++i) {
long long x1 = read(), y1 = read(), x2 = read(), y2 = read();
line[++cnt] = {x1, y1, y2, 1};
raw_y[cnt] = y1;
line[++cnt] = {x2, y1, y2, -1};
raw_y[cnt] = y2;
}
// Discretizing vertical coordinates
sort(line + 1, line + cnt + 1);
sort(raw_y + 1, raw_y + cnt + 1);
int tot = unique(raw_y + 1, raw_y + cnt + 1) - (raw_y + 1);
// The segment tree maintains intervals, tot points correspond to tot - 1 closed intervals
// The root node maintains the interval [1, tot - 1]
long long ans = 0;
for (int i = 1; i < cnt; ++i) {
// Binary locate the index of the vertical coordinate interval in the discretized array
int ql = lower_bound(raw_y + 1, raw_y + tot + 1, line[i].y1) - raw_y;
int qr = lower_bound(raw_y + 1, raw_y + tot + 1, line[i].y2) - raw_y - 1; // Critical pitfall: right boundary mapping must subtract 1
if (ql <= qr) {
update(1, 1, tot - 1, ql, qr, line[i].mark);
}
ans += len[1] * (line[i + 1].x - line[i].x);
}
printf("%lld\n", ans);
return 0;
}
NOIP Practical Pitfall Guide
1. Right Boundary Mapping of Segment Tree Not Decreased by 1 Causes Out-of-Bounds Calculation
After discretization, the leaf node $i$ of the segment tree represents the geometric interval $[raw\text{ }y[i], raw\text{ }y[i+1]]$. If a scanning line has a vertical range of $[raw\text{ }y[A], raw\text{ }y[B]]$, the target interval for update in the segment tree is $[A, B-1]$. If it is incorrectly passed as $[A, B]$, when update touches the $B^{th}$ node, the pushup formula's raw_y[r+1] will access raw_y[B+1], leading to serious logical out-of-bounds or reading garbage data.
2. Space Allocation Multiplicity Calculation Insufficient
Ordinary segment trees allocate $4$ times space. However, in the scanning line algorithm, inputting $N$ rectangles generates $2N$ edges and $2N$ vertical coordinate points. This means the base size of the original array has become $2N$. Therefore, the segment tree's array size must be allocated to $2N \times 4 = 8N$. Only allocating $4N$ will lead to direct RE when building the tree or updating deep into the right subtree.
3. Concurrent Boundary Not Handled During Horizontal Coordinate Sorting
When two rectangles have overlapping horizontal coordinates (i.e., $x_1 = x_2$) and one is an entry edge ($+1$) and the other is an exit edge ($-1$), if the exit edge is incorrectly processed first, the corresponding len[1] of the segment tree will suddenly drop to $0$, followed by an increase when processing the entry edge. This will cause a multiplication by an erroneous intermediate zero value in the computation of $\Delta x \times len[1]$. It is essential to enforce that when overloading < in the structure, entry edges are prioritized when $x$ is the same.
Classic NOIP/Luogu Problems
1. Luogu P5490 [Template] Scanning Line & Rectangle Area Union
- Problem Description: Calculate the total area covered by $N$ rectangles placed in the Cartesian coordinate system.
- Problem Essence: A standard baseline problem for the two-dimensional discretized scanning line algorithm.
- Core Solving Idea: As shown in the source code, the $y$ axis coordinates are extracted and discretized into tree node intervals. The horizontal coordinates act as event points driving the scanning line to move from left to right. Using a specialized segment tree without
pushdown, it perfectly solves the mapping and summation from high-dimensional continuous space to low-dimensional discrete space within $O(N \log N)$ complexity.
2. Luogu P1856 [IOI1998] [USACO5.5] Rectangle Perimeter Picture
- Problem Description: Calculate the total perimeter of the overall outline of the combined shapes of $N$ rectangles.
- Problem Essence: A higher-order application of scanning lines, requiring simultaneous maintenance of the covered segment length and the number of non-intersecting segments.
- Core Solving Idea: The perimeter is composed of both horizontal and vertical edges. Two scanning lines can be used to process separately, or a single vertical scan can solve simultaneously: segment tree nodes need to maintain not only
len(covered length) but alsonum(how many independent vertical segments are included in the current interval) as well asl_count,r_count(whether the left and right endpoints are covered). Each time the scanning line advances, the contribution of vertical edges is $|len_{new} - len_{old}|$, and the contribution of horizontal edges is $2 \times num \times \Delta x$.