Not Frequent

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 yy 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 xx coordinate.

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

Similarly, we decrement the counter for xx 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 [x1,x2][x_1, x_2] where x1x_1 is the lower xx coordinate and x2x_2 is the upper xx coordinate of the segment.

Our answer would be the sum of all the queries.


#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: O(P2)\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 (x1,y1)(x_1, y_1) in increasing order. It is possible to show that for all ii, jj, where i<ji < j, Bessie cannot use springboard jj then ii later.

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

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

dist(a,b)=x1[b]+y1[b]x2[a]y2[a]\texttt{dist}(a, b) = x_1[b] + y_1[b] - x_2[a] - y_2[a]

Then, the transitions are:

ans[i]=minj<i,x2[j]x1[i],y2[j]y1[i](ans[j]+dist(j,i))\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: O(PlogP)\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)dist(i, j) in the transition formula.

ans[i]=minj<i,x2[j]x1[i],y2[j]y1[i](ans[j]+x1[i]+y1[i]x2[j]y2[j])\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])
ans[i]=x1[i]+y1[i]+minj<i,x2[j]x1[i],y2[j]y1[i](ans[j]x2[j]y2[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\min statement only depends on jj. The segment tree stores ans[j]x2[j]y2[j]\texttt{ans}[j] - x_2[j] - y_2[j] at index y2[j]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)(x, y). When the event is the start of a springboard, update ans[i]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\min statement are always satisfied. The third is where the segment tree comes into play, where querying the range [0,y1[i]][0, y_1[i]] is sufficent to satisfy all constraints.

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


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


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

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


StatusSourceProblem NameDifficultyTags
Show TagsPURS
Show TagsPURQ
Show TagsPURQ

LIS Problems

StatusSourceProblem NameDifficultyTags
Balkan OIHard
Show TagsDP, PURS
Show TagsDP, PURS
PlatinumVery 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!