Overview

This problem asks us to select at most \(K\) intervals (reading plans) from a given set of \(M\) intervals, and maximize the size of their union (the total number of books covered).

By combining dynamic programming (DP) with a segment tree while accounting for overlaps between intervals, we can solve this efficiently within the time limit.

---

Analysis

1. Eliminating Redundant Intervals (Filtering)

First, if an interval \(A\) is completely contained within another interval \(B\) (\(L_B \le L_A\) and \(R_A \le R_B\)), there is no benefit in selecting interval \(A\). This is because selecting interval \(B\) instead of interval \(A\) always covers an equal or larger range.

Therefore, we eliminate redundant intervals using the following procedure: 1. Sort all intervals by “left endpoint \(L_i\) in ascending order (breaking ties by right endpoint \(R_i\) in descending order).” 2. Scan from left to right, and keep only those intervals whose right endpoint extends further right than all previously encountered right endpoints.

After this filtering, the remaining intervals (let their count be \(M'\)) satisfy the following properties: - Left endpoints are strictly increasing: \(L_1 < L_2 < \dots < L_{M'}\) - Right endpoints are also strictly increasing: \(R_1 < R_2 < \dots < R_{M'}\)

This makes the positional relationships between intervals very simple.

2. Designing the Dynamic Programming (DP)

We define the following DP table: - \(dp[j][i]\): The maximum number of books that can be covered when selecting \(j\) intervals, where the last selected interval is the \(i\)-th interval (after filtering).

When selecting the \(i\)-th interval (\([L_i, R_i]\)) as the \(j\)-th interval, let \(p\) (\(p < i\)) be the \((j-1)\)-th interval selected immediately before it. Depending on the positional relationship between interval \(p\) and interval \(i\), the number of newly added books falls into two patterns:

Pattern A: Intervals \(p\) and \(i\) do not overlap (\(R_p < L_i\))

Since the intervals do not overlap, the length of interval \(i\) is simply added as-is. $\(\text{value after transition} = dp[j-1][p] + (R_i - L_i + 1)\)\( The maximum value for this pattern is the maximum of \)dp[j-1][p]\( among all \)p\( satisfying \)R_p < L_i\(, plus \)(R_i - L_i + 1)$.

Pattern B: Intervals \(p\) and \(i\) overlap (\(R_p \ge L_i\))

Due to the filtering properties, interval \(p\) is not completely contained within interval \(i\) (\(L_p < L_i\) and \(R_p < R_i\)). Therefore, the newly covered portion excluding the overlap is \([R_p + 1, R_i]\), and the number of additional books is \(R_i - R_p\). $\(\text{value after transition} = dp[j-1][p] + (R_i - R_p) = (dp[j-1][p] - R_p) + R_i\)\( The maximum value for this pattern is the maximum of \)(dp[j-1][p] - R_p)\( among all \)p\( satisfying \)R_p \ge L_i\(, plus \)R_i$.

---

Algorithm

For each \(j\) (\(2 \le j \le K\)), we efficiently compute the values in the \(j\)-th row of the DP table from the values in the \((j-1)\)-th row.

1. Boundary Search: Use binary search (lower_bound) to find the largest index \(p\) satisfying \(R_p < L_i\) (call this p_max). This classifies the transition sources \(p\) as follows:

   • When \(p \le \text{p\_max}\): Pattern A (no overlap)
   • When \(\text{p\_max} < p < i\): Pattern B (overlap)

2. Speeding Up Pattern A: The maximum value of \(dp[j-1][p]\) for \(p \le \text{p\_max}\) can be obtained in \(O(1)\) by precomputing a prefix maximum (prefix max).

3. Speeding Up Pattern B: To find the maximum value of \(dp[j-1][p] - R_p\) for \(\text{p\_max} < p < i\), we use a segment tree. By building a segment tree loaded with the array \(A[p] = dp[j-1][p] - R_p\), we can obtain the maximum over any range \([\text{p\_max} + 1, i - 1]\) in \(O(\log M)\).

By combining these techniques, each state \(dp[j][i]\) can be computed in \(O(\log M)\).

---

Complexity

• Time Complexity: \(O(M \log M + K M \log M)\)

  • Sorting and filtering the intervals takes \(O(M \log M)\).
  • For the DP updates, the outer loop runs \(K\) times, the inner loop runs \(M'\) times (\(M' \le M\)), and each step performs a binary search and a segment tree query in \(O(\log M)\), giving an overall complexity of \(O(K M \log M)\). Since \(K \le 10\), this comfortably fits within the time limit.

• Space Complexity: \(O(K M)\) or \(O(M)\)

  • The space required to store the DP table is \(O(K M)\). This can be reduced to \(O(M)\) by only keeping the previous row.

---

Implementation Notes

• Segment Tree Initialization: To prevent transitions from unreachable DP states (values set to an extremely small negative number, -4e18 in the code), the initial values and the identity element (e()) of the segment tree should be set to a sufficiently small negative value.

• Upper Bound of \(K\): Since the total number of plans \(M'\) may be smaller than \(K\), updating \(K = \min(K, M')\) in advance prevents unnecessary computation.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;

long long op(long long a, long long b) {
    return max(a, b);
}

long long e() {
    return -4e18;
}

struct Interval {
    long long L, R;
    bool operator<(const Interval& other) const {
        if (L != other.L) return L < other.L;
        return R > other.R;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N;
    int M, K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<Interval> intervals(M);
    for (int i = 0; i < M; ++i) {
        cin >> intervals[i].L >> intervals[i].R;
    }

    sort(intervals.begin(), intervals.end());

    vector<Interval> filtered;
    long long max_R = -1;
    for (const auto& interval : intervals) {
        if (interval.R > max_R) {
            filtered.push_back(interval);
            max_R = interval.R;
        }
    }

    int M_prime = filtered.size();
    K = min(K, M_prime);

    if (M_prime == 0) {
        cout << 0 << "\n";
        return 0;
    }

    vector<long long> R_vals(M_prime);
    for (int i = 0; i < M_prime; ++i) {
        R_vals[i] = filtered[i].R;
    }

    vector<vector<long long>> dp(K + 1, vector<long long>(M_prime, -4e18));

    for (int i = 0; i < M_prime; ++i) {
        dp[1][i] = filtered[i].R - filtered[i].L + 1;
    }

    long long ans = 0;
    for (int i = 0; i < M_prime; ++i) {
        ans = max(ans, dp[1][i]);
    }

    for (int j = 2; j <= K; ++j) {
        vector<long long> max_dp(M_prime);
        max_dp[0] = dp[j-1][0];
        for (int i = 1; i < M_prime; ++i) {
            max_dp[i] = max(max_dp[i-1], dp[j-1][i]);
        }

        vector<long long> seg_init(M_prime);
        for (int i = 0; i < M_prime; ++i) {
            if (dp[j-1][i] < -2e18) {
                seg_init[i] = -4e18;
            } else {
                seg_init[i] = dp[j-1][i] - filtered[i].R;
            }
        }
        atcoder::segtree<long long, op, e> seg(seg_init);

        for (int i = 0; i < M_prime; ++i) {
            long long L_i = filtered[i].L;
            long long R_i = filtered[i].R;

            auto it = lower_bound(R_vals.begin(), R_vals.end(), L_i);
            int p_max = distance(R_vals.begin(), it) - 1;

            long long val1 = -4e18;
            if (p_max >= 0) {
                val1 = max_dp[p_max];
            }

            long long val2 = -4e18;
            int start = p_max + 1;
            int end = i;
            if (start < end) {
                long long res = seg.prod(start, end);
                if (res > -2e18) {
                    val2 = res + L_i - 1;
                }
            }

            long long best_prev = max(val1, val2);
            if (best_prev > -2e18) {
                dp[j][i] = best_prev + (R_i - L_i + 1);
            }
            ans = max(ans, dp[j][i]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.