LibreOJ 2086 「NOI2016」区间

发表于 | 分类于

Description

给你\(n\)个闭区间（第\(i\)个为\([l_i, r_i]\)），要求你选出其中\(m\)个，使得他们的交集非空。

你的得分是选出区间中最长的和最短的的长度差。请求出最优解，无解输出\(-1\)。

\(m\leq 200000, 1\leq m\leq n\leq 500000, 0\leq l_i\leq r_i\leq 10^9\)。

Solution

我们首先先把区间按长度排个序再做吧……

然后最大和最小的差，要素察觉（意味深）。two pointers，启动！

我们直接开一棵线段树，来维护每个点在当前使用区间被覆盖了多少次。在全局最大值不小于\(m\)时，开始一边更新答案一遍移动左端点。注意不合法的区间在这里一定比合法的区间答案更劣，所以直接在移动之前无脑更新答案即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 500005;
const int maxno = maxn << 3;
int maxv[maxno], addv[maxno];
void maintain(int o) {
  maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void paint(int o, int v) {
  addv[o] += v;
  maxv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    paint(o << 1, addv[o]);
    paint(o << 1 | 1, addv[o]);
    addv[o] = 0;
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    int M = (L + R) / 2;
    pushdown(o);
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 |  1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}

struct Seg {
  int l, r, len;
  bool operator <(const Seg &res) const {
    return len < res.len;
  }
};

int n, lsiz; int A2[maxn << 2];
void desc() {
  std::sort(A2 + 1, A2 + 1 + 2 * n);
  lsiz = std::unique(A2 + 1, A2 + 1 + 2 * n) - A2 - 1;
}
int query(int x) {
  return (std::lower_bound(A2 + 1, A2 + 1 + lsiz, x) - A2);
}

Seg s[maxn];
int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    int l, r; scanf("%d%d", &l, &r);
    s[i].l = l; s[i].r = r; s[i].len = r - l;
    A2[2 * i - 1] = l; A2[2 * i] = r;
  }
  desc();
  for(int i = 1; i <= n; i ++) {
    s[i].l = query(s[i].l);
    s[i].r = query(s[i].r);
  }
  std::sort(s + 1, s + 1 + n);
  int l = 1;
  int ans = INT_MAX;
  for(int r = 1; r <= n; r ++) {
    int lp = s[r].l, rp = s[r].r;
    update(1, 1, lsiz, lp, rp, 1);
    while(maxv[1] >= m) {
      ans = std::min(ans, s[r].len - s[l].len);
      update(1, 1, lsiz, s[l].l, s[l].r, -1);
      l ++;
    }
  }
  if(ans == INT_MAX) ans = -1;
  printf("%d\n", ans);
  return 0;
}