# Range Queries with Sweep Line

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

Solving 2D grid problems using 1D range queries.

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.

## Implementation

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

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$.

Then, the transitions are:

**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.

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:

- Add a pair $(a,b)$.
- 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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

HE | Easy | ## Show TagsPURS | |||

Platinum | Normal | ## Show TagsPURQ | |||

Platinum | Normal | ||||

CSES | Hard | ## Show TagsPURQ | |||

IZhO | Hard | ## Show TagsLazy SegTree, PURQ, Stack |

### LIS Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Balkan OI | Hard | ## Show TagsDP, PURS | |||

COCI | Hard | ## Show TagsDP, PURS | |||

Platinum | Very Hard | ## Show TagsDP |

### Module Progress:

### 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!