PrevNext
Not Frequent
 0/10

Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu, Dong Liu

Solving 2D grid problems using 1D range queries.

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

Focus Problem – try your best to solve 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

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.

C++

#include <bits/stdc++.h>
using namespace std;
int bit[2000005];
void update(int i, int x) {
for (; i < 2000005; i += i & (-i)) bit[i] += x;
}
int query(int i) {
int sum = 0;

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 NameDifficultyTags
HEEasy
Show TagsPURS
PlatinumNormal
Show TagsPURQ
PlatinumNormal
CSESHard
Show TagsPURQ
IZhOHard

Relating to LIS:

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

PrevNext