PrevNext
Not Frequent
 0/9

Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu

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)(a,b).
  2. For any xx, query the minimum value of bb over all pairs satisfying axa\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

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!

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.

PrevNext