「USACO 2010」农场分配【线段树】

Time Limit: 3 Sec Memory Limit: 64 MB

Description

畜栏包括 NN 个畜栏 (1N1051 \leqslant N \leqslant 10^5),我们把它们编号为 1...N1...N,畜栏 ii 能容纳 CiC_i 只牛 (1Ci1051 \leqslant C_i \leqslant 10^5),第 ii 只牛需要连续编号畜栏 (从 AiA_iBiB_i) 来漫步其中 (1AiBiN1 \leqslant A_i \leqslant B_i \leqslant N)。换言之,这只牛想要在编号范围为 AiA_iBiB_i 的畜栏漫步 (漫步所有它想要畜栏必须实施为它空出位置来供它散步)。

给出 MM 个畜栏分配请求 (1M1051 \leqslant M \leqslant 10^5),回答最多能满足多少只牛的要求 (不增加另外的畜栏)。

考虑以下例子:

1
2
3
4
5
6
7
8
畜栏号:       1   2   3   4   5
+---+---+---+---+---+
容纳空间: | 1 | 3 | 2 | 1 | 3 |
+---+---+---+---+---+
Cow 1 XXXXXXXXXXX (1, 3)
Cow 2 XXXXXXXXXXXXXXX (2, 5)
Cow 3 XXXXXXX (2, 3)
Cow 4 XXXXXXX (4, 5)

显然不能满足所有的牛,因为畜栏 3,43, 4 请求太多了。经过试验,我们发现,我们能满足牛 1,3,41, 3, 4 的需要,所以这组数据答案为 33

Input

11 行:以空格隔开的两个正整数:N,MN, M
22N+1N+1 行:第 i+1i+1 行包括一个整数 CiC_i
N+2N+2N+M+1N+M+1 行:第 i+N+1i+N+1 行包括两个整数 Ai,BiA_i, B_i

Output

11 行: 一个整数,表示最多能够被满足的要求数。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

Sample Output

1
3

Solution

贪心 + 线段树:

  • 对于所有的线段,将其按照右端点排序,然后贪心的选择 (证明略)。
  • 从前往后扫描,如果能够取当前线段就取,并更新 CiC_i,如果不能取就看下一个。
  • 可以通过线段树维护 (区间更新, 区间查询),多记录一个每个位置有多少空位 (区间最小值)。
  • 每次查询时看区间最小值是否大于 00,大于 00 则表示可以放该线段,否则不能放。
  • 排序和线段树的时间复杂度为 O(mlogn+mlogm)O(m \cdot \log n+m \cdot \log m)
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
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, m, res;
struct cow {
int l, r;
bool operator < (const cow &other) const {
return r < other.r;
}
} c[maxn];
struct segment_tree {
int l, r, mn, lazy;
} tree[maxn << 2];

void build(int k, int l, int r) {
tree[k].l = l;
tree[k].r = r;
if (l == r) {
scanf("%d", &tree[k].mn);
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
tree[k].mn = min(tree[k << 1].mn, tree[k << 1 | 1].mn);
}

void pushdown(int k) {
if (tree[k].l < tree[k].r && tree[k].lazy) {
tree[k << 1].lazy += tree[k].lazy;
tree[k << 1].mn -= tree[k].lazy;
tree[k << 1 | 1].lazy += tree[k].lazy;
tree[k << 1 | 1].mn -= tree[k].lazy;
tree[k].lazy = 0;
}
}

void update(int k, int l, int r) {
pushdown(k);
if (tree[k].l == l && tree[k].r == r) {
tree[k].mn--;
tree[k].lazy++;
return;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
update(k << 1, l, r);
} else if (mid < l) {
update(k << 1 | 1, l, r);
} else {
update(k << 1, l, mid);
update(k << 1 | 1, mid + 1, r);
}
tree[k].mn = min(tree[k << 1].mn, tree[k << 1 | 1].mn);
}

bool query(int k, int l, int r) {
pushdown(k);
if (tree[k].l == l && tree[k].r == r) {
return tree[k].mn >= 1;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
return query(k << 1, l, r);
} else if (mid < l) {
return query(k << 1 | 1, l, r);
} else {
return query(k << 1, l, mid) && query(k << 1 | 1, mid + 1, r);
}
}

int main() {
scanf("%d %d", &n, &m);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &c[i].l, &c[i].r);
}
sort(c + 1, c + m + 1);
for (int i = 1; i <= m; i++) {
if (query(1, c[i].l, c[i].r)) {
update(1, c[i].l, c[i].r);
res++;
}
}
printf("%d\n", res);
return 0;
}