线段树应用之颜色数量

缘起

面试题

1
2
x轴上有若干条不同线段，将它们依次染上不同的颜色，问最后能看到多少种不同的颜色？（后染的颜色会覆盖原先的
颜色）

分析

显然，这里应该使用【1】中介绍的区间线段树来搞. 因为区间线段树关注的是区间，没有缝隙.

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
#include "stdafx.h"
#include<iostream>
#include <stdio.h>
#define LOCAL

using namespace std;

const int MAX_LEN = 20; // 线段最大跨度不超过20

bool color[MAX_LEN]; // color[i]为true表示第i种颜色出现了. 否则表示没出现, 其实就是一张哈希表

struct
{
	int begin, end;
	int color; // 染上的颜色
} segmenttree[MAX_LEN<<2];

inline int getmid(int i) {return (segmenttree[i].begin+segmenttree[i].end)>>1;}

void build(int begin, int end, int root)
{
	segmenttree[root].begin = begin;
	segmenttree[root].end = end;
	segmenttree[root].color = 0;
	if (begin+1==end) return; // 区间线段树的叶子是一个个单位长度的区间
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1);
	build(mid, end, (root<<1)+1);// 左孩子是 [beign,mid] 右孩子是 [mid,end]
}

void pushdown(int i)
{
	segmenttree[i<<1].color = segmenttree[(i<<1)+1].color = segmenttree[i].color; // 对应图1情形1，左右孩子都继承当前节点的颜色
	segmenttree[i].color = 0; // 当前节点失色
}

void insert(int begin,int end, int color, int i) // 将染有color色的[begin,end]插入线段树
{
	if (segmenttree[i].begin == begin && segmenttree[i].end == end) // 如果完全覆盖的话
	{
		segmenttree[i].color = color; // segmenttree[i]就染上色了
		return;
	}
	if (segmenttree[i].color) pushdown(i); // 如果当前节点有颜色的话, 则不论是图1的情形1还是情形2还是情形3, 都要下推, 即左右孩子继承当前节点的颜色, 并且当前节点失色（因为已经变成杂色了嘛~）.
	// 否则, [begin,end]就是当前线段的真子集, 则如果当前线段原先持有一种颜色segmenttree[i].color, 则当前线段就不能继续持有颜色segmenttree[i].color了（因为已经变成杂色了嘛）
	int mid = getmid(i);
	if (mid>=end) insert(begin, end, color, i<<1);
	else if (begin>=mid) insert(begin, end, color, (i<<1)+1);
	else  // begin<mid<end, 则线段[begin,end]被[begin,mid]和[mid,end]剖分
	{
		insert(begin, mid, color,i<<1);
		insert(mid, end, color, (i<<1)+1);
	}
}

bool colorstatistics(int i) // 统计线段树总共几种颜色
{
	if (segmenttree[i].begin+1==segmenttree[i].end) return color[segmenttree[i].color] = true; // 如果到了叶子节点,如果没染色的话, 就是color[0]=true, 但是我们合法的颜色是从1开始的（每条线段的颜色都不一样, 从1开始递增的那种）所以不影响最后的统计
	if (segmenttree[i].color) return color[segmenttree[i].color] = true; // 如果当前节点对应的线段已经有了颜色的话, 则这种颜色就使用过了.注意，这里直接返回了, 就不会再管子节点是什么颜色了, 这就是题目说的后面来的线段可能覆盖前面线段染的色
	return colorstatistics(i<<1) && colorstatistics((i<<1)+1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int begin[10] = {1,2,3}, end[10]={3,3,6}; // 这里的测试数据模拟的是[1,3]这条线段染一种样色，然后[2,3]又染一中样色（则将之前染的颜色覆盖掉了）, 最后[3,6]上一中颜色, 则总共就有2种颜色了
	build(1, 6, 1);
	for (int i = 0; i<3; i++)
	{
		insert(begin[i], end[i],i+1,1);
	}
	colorstatistics(1); // 统计总共几种颜色
	int sum = 0;
	for (int i = 1; i<= 3;i++)sum+=color[i]; // 颜色总共三种,和线段条数一致. 
	printf("%d\n", sum);
	return 0;
}

​ 图1

参考

【1】https://yfsyfs.github.io/2019/07/14/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%BA%94%E7%94%A8%E4%B9%8B%E7%BA%BF%E6%AE%B5%E8%A6%86%E7%9B%96%E6%80%BB%E9%95%BF%E5%BA%A6%EF%BC%88%E5%8F%A6%E4%B8%80%E7%A7%8D%E5%BB%BA%E6%A0%91%E6%96%B9%E5%BC%8F%EF%BC%89/