Keywords: Segment tree

题目来源:POJ
题意:在墙上贴海报,后贴的会覆盖之前的,问最后能看见几张海报

20170515 Update:
NotOnlySuccess菊苣的博客打不开了,不清楚情况。话说菊苣现在在微信啊,膜拜。想看菊苣的文章的话,建议以 ”notonlysuccess 【完全版】线段树“ 为关键词进行搜索。


线段树染色问题,注意题目里每个数字代表一个单位长度而不是点,普通离散化会出现问题。以下例子来自NotOnlySuccess菊苣的博客

例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了$[1,4][1,2][3,4]$
线段2覆盖了$[1,2]$, 线段3覆盖了$[3,4]$, 那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖

针对这个问题,网上常见的做法是对离散化的数组做一个小处理。以下同样来自NotOnlySuccess菊苣的博客

为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说$[1,2,6,10]$
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成$[1,2,3,6,7,10]$,然后再做线段树就好了.

但是,这样做会增加 maxn 的大小,难以忍受……

事实上,只要在输入$[l, r]$的时候进行处理,变成$[l, r + 1]$,相当于线段树存储的是一整段区间的信息(传说中的“段树”),就可以应用普通离散化了,具体见代码

另外,由于POJ这题数据奇弱无比,一种叫做浮水法的 $n^2$ 的做法也是可以过的,这个是我搜本题题解的时候搜到的一种做法,网上资料很少,下面同样附上代码和本人的理解o( ̄▽ ̄)ブ

浮水法:本题中,将每条线段和其后的线段进行比较,没有重叠部分就继续和下一条比较,有重叠部分则去掉重叠部分再继续比较,比较是递归的。这个递归过程就像一层一层上浮最后浮到水面上一样,所以叫浮水法(让人联想到冒泡啊)。如果某条线段最后能浮到水面上,ans++

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
89
90
91
92
93
94
95
96
97
// 线段树
// 省略头文件
#define ALL(v) v.begin(), v.end()
#define CLR(array) memset(array, 0, sizeof(array))
#define DEBUG cout << "bug "
#define Fr first
#define FOR(i, n) for(int i = 0; i < n; i++)
#define MEM(array) memset(array, 0x3f, sizeof(array))
#define ls L(id)
#define lson id << 1, l, mid
#define OFF(array) memset(array, -1, sizeof(array))
#define PR(x) cout << #x << " = " << x << " "
#define PRLN(x) cout << #x << " = " << x << endl
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define root 1, 1, n
#define rs R(id)
#define rson id << 1 | 1, mid, r // 注意这里是 mid
#define Rep(i, a, b) for(int i = a; i >= b; i--)
#define repk(i, a, b) for(i = a; i <= b; i++)
#define Repk(i, a, b) for(i = a; i >= b; i--)
#define Sc second
#define SZ size()
using namespace std;
inline int L(int x){ return x << 1; }
inline int R(int x){ return x << 1 | 1; }
inline int MID(int l, int r){ return l + r >> 1; }
typedef long long ll;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f, maxn = 2e4 + 5;
int color[maxn << 2];
int x[maxn >> 1], y[maxn >> 1];
int vis[maxn >> 1];
void push_down(int id) {
color[ls] = color[rs] = color[id];
color[id]= -1;
}
void update(int id, int l, int r, int a, int b, int val) {
if(a <= l && r <= b) {
color[id] = val;
return;
}
if(r > l && ~color[id]) push_down(id);
int mid = MID(l, r);
if(mid > a) update(lson, a, b, val);
//第一次写段树,一开始总是莫名崩溃,后来发现此处的判断跟点树不一样,不应该有等号,否则会无限递归 -> 越界
if(mid < b) update(rson, a, b, val);
}
void query(int id, int l ,int r) {
if(~color[id]) {
vis[color[id]] = 1;
return;
}
if(l + 1 == r) return;
int mid = MID(l, r);
query(lson);
query(rson);
}
int compress(int m) { // 离散化部分
vector<int> v;
FOR(i, m) {
scanf("%d%d", x + i, y + i);
y[i]++; // 此处 +1, 使 x[i], y[i] 表示区间的左右端点
v.push_back(x[i]);
v.push_back(y[i]);
}
sort(ALL(v));
v.resize(unique(ALL(v)) - v.begin());
FOR(i, m) {
x[i] = 1 + lower_bound(ALL(v), x[i]) - v.begin();
y[i] = 1 + lower_bound(ALL(v), y[i]) - v.begin();
}
return v.SZ;
}
int solve(void) {
int n, m, ans = 0;
scanf("%d", &m);
n = compress(m);
color[1] == m; //开始全部无色,用 m 表示
FOR(i, m) update(root, x[i], y[i], i);
CLR(vis);
query(root);
FOR(i, m) if(vis[i]) ans++;
return ans;
}
int main(void) {
//freopen("F:\\Desktop\\in.txt", "r", stdin);
int t; scanf("%d", &t);
while(t--) printf("%d\n", solve());
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
// 浮水法
// 此处省略50行头文件及宏
const int inf = 0x3f3f3f3f, maxn = 1e4 + 5;
int a[maxn], b[maxn];
int n;
int cover(int l, int r, int id) {
if(id > n) return 1;
int nowl = a[id], nowr = b[id];
if(l > nowr || r < nowl) return cover(l, r, id + 1);
if(r > nowr && cover(nowr + 1, r, id + 1)) return 1;
if(nowl > l && cover(l, nowl - 1, id + 1)) return 1;
return 0;
}
int solve(void) {
int ans = 0;
scanf("%d", &n);
rep(i, 1, n) scanf("%d%d", a + i, b + i);
rep(i, 1, n)
if(cover(a[i], b[i], i + 1)) ans++;
return ans;
}
int main(void) {
//freopen("F:\\Desktop\\in.txt", "r", stdin);
int t; scanf("%d", &t);
while(t--) printf("%d\n", solve());
return 0;
}