Not Frequent
0/10

# Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu, Dong Liu, Peng Bai

Solving 2D grid problems using 1D range queries.

### Prerequisites

Focus Problem – try your best to solve this problem before continuing!

## Solution - Intersection Points

We can sweep from bottom to top (by the $y$ coordinate); storing two events for vertical segments (one for start and one for end) and one event for horizontal segments.

We can use a Binary Indexed Tree to store the number of active vertical segments for each $x$ coordinate.

Then, every time we encounter the start of a vertical segment, we increment the counter for $x$ in the BIT.

Similarly, we decrement the counter for $x$ every time we see the end of a vertical segment.

When we encounter a horizontal segment, we would query the number of active ranges in $[x_1, x_2]$ where $x_1$ is the lower $x$ coordinate and $x_2$ is the upper $x$ coordinate of the segment.

Our answer would be the sum of all the queries.

C++

#include <bits/stdc++.h>using namespace std;
Code Snippet: BIT (from the PURS module) (Click to expand)
const int MAX_POS = 1e6;
int main() {	int n;	cin >> n;

Focus Problem – try your best to solve this problem before continuing!

## Solution - Springboards

Naive DP: $\mathcal{O}(P^2)$

The first step is to create a DP to solve the first subtask. The states are the springboards and the transitions are between springboards. First, sort the springboards by the pair $(x_1, y_1)$ in increasing order. It is possible to show that for all $i$, $j$, where $i < j$, Bessie cannot use springboard $j$ then $i$ later.

For each springboard $i$, let $\texttt{ans}[i]$ denote the minimum distance needed to walk to the start point of springboard $i$.

Let $\texttt{dist}(a, b)$ be the walking distance from the end of springboard $a$ and the start of springboard $b$.

$\texttt{dist}(a, b) = x_1[b] + y_1[b] - x_2[a] - y_2[a]$

Then, the transitions are:

$\texttt{ans}[i] = \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(ans[j] + \texttt{dist}(j, i))$

Full Solution: $\mathcal{O}(P \log P)$

Optimizing the DP involves the use of a min point update range query segment tree. Let's first expand $dist(i, j)$ in the transition formula.

$\texttt{ans}[i] = \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(\texttt{ans}[j] + x_1[i] + y_1[i] - x_2[j] - y_2[j])$
$\texttt{ans}[i] = x_1[i] + y_1[i] + \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(\texttt{ans}[j] - x_2[j] - y_2[j])$

We notice that everything inside the $\min$ statement only depends on $j$. The segment tree stores $\texttt{ans}[j] - x_2[j] - y_2[j]$ at index $y_2[j]$. We can seperate the start and end of springboards to create two seperate events for each springboard, still sorting by $(x, y)$. When the event is the start of a springboard, update $ans[i]$ through a segment tree query. When the event is the end of a springboard, update the segment tree.

By processing in order, the first two conditions in the $\min$ statement are always satisfied. The third is where the segment tree comes into play, where querying the range $[0, y_1[i]]$ is sufficent to satisfy all constraints.

Due to the large $N$, coordinate compression is required in the code.

### Implementation

Time Complexity: $\mathcal{O}(P \log P)$

C++

#include <bits/stdc++.h>using namespace std;
Code Snippet: Segment Tree (from the PURS module) (Click to expand)
struct Point {	int x, y;	int i;	bool is_start;


### Alternate Approach

It turns out there is also a simpler though less straightforward method to solve this problem.

The problem boils down to having a data structure that supports the following operations:

1. Add a pair $(a,b)$.
2. For any $x$, query the minimum value of $b$ over all pairs satisfying $a\le x$.

This solution is described in the official editorial and the other module.

## Problems

StatusSourceProblem NameDifficultyTags
HEEasy
Show TagsPURS
PlatinumNormal
Show TagsPURQ
PlatinumNormal
CSESHard
Show TagsPURQ
IZhOHard

### LIS Problems

StatusSourceProblem NameDifficultyTags
Balkan OIHard
Show TagsDP, PURS
COCIHard
Show TagsDP, PURS
PlatinumVery Hard
Show TagsDP

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!