ARC076F Exhausted?

发表于 | 分类于

Description

有\(n\)个人和\(m\)张椅子，第\(i\)个人想要坐编号在\([1, L_i]\cup [R_i, m]\)中的椅子。请合理安排，使得坐不上椅子的人尽可能少（你可以让一个人不坐椅子）。

\(1\leq n, m\leq 200000, 0\leq L_i<R_i\leq m + 1\)。

Solution

Hall定理有这么一个拓展：对于二分图\((S\cup T, E)\)，其最大匹配数为\(|S| - \max\{|S'| - |\Gamma(S')|(S'\subseteq S)\}\)，其中\(\Gamma(A)\)表示\(T\)中有多少点和\(A\)中的点有边相连。

那么考虑应用到这个题上……最后\(\Gamma(S')\)的形态肯定是\([1, l]\cup [r, m]\)这样，\(\Gamma(S')\)确定之后\(S'\)中所有的\(i\)都要满足\(L_i\leq l\land R_i\geq r\)。因此我们考虑从大到小枚举\(r\)，那么可以用的点就能确定了。然后再去考虑\(l\)的贡献，很显然可以用线段树维护一下……

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
const int maxn = 200005;
const int maxno = maxn << 2;
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) {
  maxv[o] += v; addv[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 build_tree(int o, int L, int R) {
  addv[o] = 0;
  if(L == R) {
    maxv[o] = -L + 1;
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, const int &ql, const int &qr, const 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);
  }
}
int query(int o, int L, int R, const int &ql, const int &qr) {
  if(ql <= L && R <= qr) {
    return maxv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = -0x7fffffff;
    if(ql <= M) ans = std::max(ans, query(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

std::vector<int> V[maxn];
int main() {
  int n, m; scanf("%d%d", &n, &m);
  build_tree(1, 1, m + 1);
  for(int i = 1; i <= n; i ++) {
    int L, R; scanf("%d%d", &L, &R);
    V[R].push_back(L);
  }
  int ans = n - m;
  for(int i = m + 1; i >= 1; i --) {
    int bs = -(m - i + 1);
    for(int p : V[i]) {
      update(1, 1, m + 1, p + 1, m + 1, 1);
    }
    bs += query(1, 1, m + 1, 1, i - 1 + 1);
    ans = std::max(ans, bs);
  }
  printf("%d\n", ans);
  return 0;
}