Range Queries with Sweep Line

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

Copy
#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;

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

Copy
#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)$.
2. 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

LIS Problems