poj2528 线段树+离散化

112 阅读 0 评论 74 点赞

我是靠谱客的博主激昂毛豆，这篇文章主要介绍poj2528 线段树+离散化，现在分享给大家，希望可以做个参考。

题意：n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000)。

求出最后还能看见多少张海报。

输入：

复制代码

解法：离散化，如下面的例子（题目的样例），因为单位1是一个单位长度，将下面的

1 2 3 4 6 7 8 10

— — — — — — — —

1 2 3 4 5 6 7 8

离散化 X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10

于是将一个很大的区间映射到一个较小的区间之中了，然后再对每一张海报依次更新在宽度为1~8的墙上(用线段树），最后统计不同颜色的段数。

但是只是这样简单的离散化是错误的，

如三张海报为：1~10 1~4 6~10

离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。

新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）

X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10

这样之后，第一次是1~5被染成1；第二次1~2被染成2；第三次4~5被染成3

最终，1~2为2，3为1，4~5为3，于是输出正确结果3。

复制代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define M 10005
int m, li[M], ri[M];
int x[M<<3], col[M<<4], ans;
bool hash[M];
void PushDown(int rt) {
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
void Update(int L, int R, int c, int l, int r, int rt) {
if (l >= L && r <= R) {
col[rt] = c;
return;
}
if (col[rt] != -1) PushDown(rt);
int m = (l + r) >> 1;
if (m >= L) Update(L, R, c, l, m, rt<<1);
if (m < R)
Update(L, R, c, m+1, r, rt<<1|1);
}
void query(int l, int r, int rt) {
if (l == r) {
if (!hash[col[rt]]) {
ans++;
hash[col[rt]] = true;
}
return;
}
if (col[rt] != -1) PushDown(rt);
int m = (l + r) >> 1;
query(l, m, rt<<1);
query(m+1, r, rt<<1|1);
}
int BSearch(int ll, int hh, int xx) {
int mm;
while (ll <= hh) {
mm = (ll + hh) >> 1;
if (x[mm] == xx) return mm;
else if (x[mm] > xx)
hh = mm - 1;
else ll = mm + 1;
}
return -1;
}
int main()
{
int t, n, i;
scanf ("%d", &t);
while (t--) {
memset(col, -1, sizeof (col));
memset (hash, false, sizeof (hash));
int nn = 0;
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d %d", &li[i], &ri[i]);
x[++nn] = li[i];
x[++nn] = ri[i];
}
sort(x+1, x+nn+1);
m = 1;
for (i = 2; i <= nn; i++) {
if (x[i] != x[i-1]) x[++m] = x[i];
}
for (i = m; i > 1; i--) {
if (x[i] - x[i-1] > 1) x[++m] = x[i] - 1;
}
sort(x+1, x+m+1);
for (i = 1; i <= n; i++) {
int l = BSearch(1, m, li[i]);
int r = BSearch(1, m, ri[i]);
Update(l, r, i, 1, m, 1);
}
ans = 0;
query(1, m, 1);
printf("%dn", ans);
}
return 0;
}

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define M 10005
int m, li[M], ri[M];
int x[M<<3], col[M<<4], ans;
bool hash[M];
void PushDown(int rt) {
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
void Update(int L, int R, int c, int l, int r, int rt) {
if (l >= L && r <= R) {
col[rt] = c;
return;
}
if (col[rt] != -1) PushDown(rt);
int m = (l + r) >> 1;
if (m >= L) Update(L, R, c, l, m, rt<<1);
if (m < R)
Update(L, R, c, m+1, r, rt<<1|1);
}
void query(int l, int r, int rt) {
if (l == r) {
if (!hash[col[rt]]) {
ans++;
hash[col[rt]] = true;
}
return;
}
if (col[rt] != -1) PushDown(rt);
int m = (l + r) >> 1;
query(l, m, rt<<1);
query(m+1, r, rt<<1|1);
}
int BSearch(int ll, int hh, int xx) {
int mm;
while (ll <= hh) {
mm = (ll + hh) >> 1;
if (x[mm] == xx) return mm;
else if (x[mm] > xx)
hh = mm - 1;
else ll = mm + 1;
}
return -1;
}
int main()
{
int t, n, i;
scanf ("%d", &t);
while (t--) {
memset(col, -1, sizeof (col));
memset (hash, false, sizeof (hash));
int nn = 0;
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d %d", &li[i], &ri[i]);
x[++nn] = li[i];
x[++nn] = ri[i];
}
sort(x+1, x+nn+1);
m = 1;
for (i = 2; i <= nn; i++) {
if (x[i] != x[i-1]) x[++m] = x[i];
}
for (i = m; i > 1; i--) {
if (x[i] - x[i-1] > 1) x[++m] = x[i] - 1;
}
sort(x+1, x+m+1);
for (i = 1; i <= n; i++) {
int l = BSearch(1, m, li[i]);
int r = BSearch(1, m, ri[i]);
Update(l, r, i, 1, m, 1);
}
ans = 0;
query(1, m, 1);
printf("%dn", ans);
}
return 0;
}

然后再提一下我自己关于二分理解(对二分总是理解不透彻,需要慢慢积累）：

最初二分写成这样的，老是错：

复制代码

1
2
3
4
5
6
7
8
9
10
11
int BSearch(int ll, int hh, int xx) {
int mm;
while (ll < hh) {
mm = (ll + hh) >> 1;
if (x[mm] == xx) return mm;
else if (x[mm] > xx)
hh = mm;
else ll = mm + 1;
}
return -1;
}

后来理解之后，才发现，这样写，只能搜索在区间[ll,hh)的数，注意，右边是开区间，而此题正好需要搜索右边的闭区间，所以错了。

之前的思想以及代码参考：神牛博客

http://www.notonlysuccess.com/index.php/segment-tree-complete/