[Codeforces1055E] Segments on the Line

给定给 (n) 个点，以及 (m) 条线段，选择 (s) 条线段，使得至少被一个线段覆盖的点的坐标从小到大排序后，第 (k) 大最小，没有则输出 (-1)。

(n, m, s, k leq 1500)。

二分答案 (ans)，判断是否存在一个方案使小于等于 (ans) 的被覆盖的点数大于等于 (k)。

设 (dp[i][j]) 表示选了 (i) 条线段，右端点都小于等于 (j) 的最多点数。

考虑线段 ([l, j]) 时：

[dp[i][j] = max_{k = l}^j {dp[i - 1][k - 1] + cnt_{k, j}} ]

这个可以用单调队列优化。

但是实际上在前面的 (1dots i - 1) 都考虑过的情况下，如果一个点 (i) 被覆盖，那覆盖这个点的线段的右端点一定越大越好，所以只需要每次更新的最大右端点处的 dp 值即可。

#include <bits/stdc++.h>
#define dbg(...) std::cerr << " 33[32;1m", fprintf(stderr, __VA_ARGS__), std::cerr << " 33[0m"
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
using LL = long long;
using PII = std::pair<int, int>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, s, k;
  std::cin >> n >> m >> s >> k;
  std::vector<int> a(n), rb(n, -1);
  int l = 1, r = 0;
  for (auto &x : a) std::cin >> x, smax(r, x);
  while (m--) {
    int x, y; std::cin >> x >> y;
    for (int i = x - 1; i < y; i++) smax(rb[i], y - 1);
  }
  int ans = -1;
  while (l <= r) {
    int m = l + r >> 1;
    std::vector<int> b(n), f(n);
    for (int i = 0; i < n; i++) {
      b[i] = (i ? b[i - 1] : 0) + (a[i] <= m);
    }
    for (int i = 0; i < s; i++) {
      for (int j = n - 1; j >= 0; j--) {
        if (rb[j] == -1) continue;
        smax(f[rb[j]], j ? f[j - 1] + b[rb[j]] - b[j - 1] : b[rb[j]]);
      }
      for (int j = 1; j < n; j++) {
        smax(f[j], f[j - 1]);
      }
    }
    if (f.back() >= k)
      r = m - 1, ans = m;
    else
      l = m + 1;
  }
  std::cout << ans << "
";
  return 0;
}

[Codeforces1055E] Segments on the Line

相关推荐