Minimal Segment Cover -- CF 1175E

Difficulty: 2000 * Techniques: greedy interval covering, binary lifting, prefix-max sweep Problem Link

Quick Revisit

• PROBLEM: Minimum segments to cover [x, y], answering many queries
• KEY INSIGHT: Greedy jump function (reach[p] = farthest right from p) + binary lifting for O(log n) per query
• TECHNIQUES: greedy interval covering, binary lifting, prefix-max sweep
• TRANSFER: "Repeated function application" = binary lifting. Interval covering + fast queries = this template.

First Read

We have $n$ segments $[l_i,r_i]$ and $m$ queries, each asking: "What's the minimum number of segments to cover $[x,y]$?" Segments can overlap, and coordinates go up to $5\times {10}^5$.

Classic interval covering -- the greedy is well-known. But $m$ can be $2\times {10}^5$ and the greedy is $O(n)$ per query in the worst case. We need to answer queries fast.

The Naive Greedy

Standard interval covering: start at $x$, find the segment starting at or before your current position that extends farthest right, jump there, repeat until you pass $y$.

Each "jump" is: from position $p$, find $max(r_i)$ over all segments with $l_i\le p$. If we precompute $\text{reach}[p]$ = farthest right endpoint among segments with left endpoint $\le p$, then a jump from $p$ goes to $\text{reach}[p]$.

But in the worst case, we might make $O(n)$ jumps per query. Too slow.

The Aha Moment: Binary Lifting

Each jump is a function: position $p\to \text{reach}[p]$. We want to do many jumps quickly. That's exactly what binary lifting does -- precompute the result of $2^k$ jumps from each position.

Define:

• $\text{jump}[p][0]=\text{reach}[p]$ -- one jump from $p$.
• $\text{jump}[p][k]=\text{jump}[\text{jump}[p][k-1]][k-1]$ -- $2^k$ jumps from $p$.

To answer query $[x,y]$: start at $x$, use binary lifting to take the fewest jumps that get us past $y$. Standard "decompose into powers of 2" technique.

I love when two seemingly unrelated ideas (interval greedy + binary lifting from LCA) combine like this.

Building the reach Array

We don't want to store all segments and scan them. Instead:

1. For each coordinate $c$: $\text{reach}[c]=max(r_i)$ over segments with $l_i=c$.
2. Then sweep left to right: $\text{reach}[c]=max(\text{reach}[c],\text{reach}[c-1])$.

After the sweep, $\text{reach}[c]$ = farthest right endpoint reachable using a single segment whose left endpoint is at or below $c$. That is the jump function.

Coordinate convention. This problem uses closed integer intervals $[l,r]$ (Codeforces convention). The query asks to cover $[x,y]$ with segments, treating cover as full closed-interval inclusion. The jump from $p$ "covers up to and including" $\text{reach}[p]$, so the next uncovered point conceptually is $\text{reach}[p]+1$ (when it exists). Because we only ever compare reach values to the query right endpoint $y$, it is cleaner to work with $\text{reach}[p]$ directly as "farthest closed right endpoint covered" and treat the loop as "advance until $\text{reach}[p]\ge y$." Be deliberate here: if you ever switch to half-open conventions or to "next uncovered = $\text{reach}[p]+1$," every subsequent comparison flips by one and the binary-lifting indices have to follow.

Answering a Query

From position $x$, iterate $k$ from high to low. If $\text{jump}[x][k]<y$, take the jump (add $2^k$ to answer, update $x$). After all bits, take one more step. If $x$ still doesn't reach $y$, output $-1$.

Implementation Notes

• Coordinates up to $5\times {10}^5$, so the array is manageable.
• $\text{reach}[c]$ should start as $c$ (you're already at $c$, so worst case you reach $c$). If $\text{reach}[c]=c$ after processing, it means no segment covers $c$, so a query requiring coverage of $c$ is impossible.
• LOG = 19 works because $2^{19}=524288>5\times {10}^5$, but it is brittle as a teaching constant -- one tweak to MAXC and the table silently truncates. Prefer a computed LOG = __lg(MAXC) + 1 or a visibly conservative LOG = 20 (or 21) so the code stays correct under coordinate changes.

The Code

#include <bits/stdc++.h>
using namespace std;

const int MAXC = 5e5 + 1, LOG = 19;
int reach[MAXC + 1];
int jp[MAXC + 1][LOG];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i <= MAXC; i++) reach[i] = i;
    for (int i = 0; i < n; i++) {
        int l, r; scanf("%d%d", &l, &r);
        reach[l] = max(reach[l], r);
    }
    for (int i = 1; i <= MAXC; i++)
        reach[i] = max(reach[i], reach[i - 1]);

    for (int i = 0; i <= MAXC; i++) jp[i][0] = reach[i];
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i <= MAXC; i++)
            jp[i][k] = jp[min(jp[i][k-1], MAXC)][k-1];

    while (m--) {
        int x, y; scanf("%d%d", &x, &y);
        if (reach[x] == x && x != y) { printf("-1\n"); continue; }
        int ans = 0, cur = x;
        for (int k = LOG - 1; k >= 0; k--) {
            if (jp[cur][k] < y) {
                cur = jp[cur][k];
                ans += (1 << k);
            }
        }
        if (cur < y) { cur = jp[cur][0]; ans++; }
        printf("%d\n", cur >= y ? ans : -1);
    }
}

Transfer Lesson

• Repeated application of a function -- whenever you're "jumping" from state to state and need to do it fast, binary lifting is the tool.
• Interval covering queries = greedy jump function + binary lifting. This is a reusable template.
• Preprocessing the reach array with a prefix-max sweep avoids sorting or scanning segments per query.

---

See also: Greedy | Binary Lifting / LCA | Prefix Sums | Pattern Recognition Guide | Practice Ladder 1700-2100