Not Frequent
0/9

# Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu

### Prerequisites

Solving 2D grid problems using 1D range queries.

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

## Tutorial

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

## Solution - Intersection Points

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

## Solution - Springboards

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

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

The other module describes a simpler way of doing this, though it's probably more straightforward to do coordinate compression and use a min segtree. The latter approach is shown below.

/** * Description: 1D point update, range query where \texttt{comb} is    * any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}. * Time: O(\log N) * Source:    * http://codeforces.com/blog/entry/18051    * KACTL * Verification: SPOJ Fenwick */


## Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
HEEasy
PlatNormal
Show Tags

PURQ

External Sol
CSESHard
Show Tags

PURQ

View Solution
IZhOHardView Solution

Relating to LIS:

StatusSourceProblem NameDifficultyTagsSolutionURL
Balkan OIHard
Show Tags

DP, BIT

External Sol
COCIHard
Show Tags

DP, BIT

External Sol
PlatVery Hard
Show Tags

DP

External Sol

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

## Give Us Feedback on Range Queries with Sweep Line!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.