线段树应用之线段覆盖总长度

缘起

【1】中我们使用了贪心算法在O(nlogn)时间内解决了这个问题. 本文使用线段树再次蹂躏它一次.

分析

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

using namespace std;

const int MAX_LEN = 100;

int res;

struct
{
	int begin, end; 
	int cover;
	bool add;

} 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)
{
	if (begin > end) return;
	segmenttree[root].begin = begin;
	segmenttree[root].end = end;
	segmenttree[root].cover = 0;
	if (begin==end) return;
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1);
	build(mid+1, end, (root<<1)+1);
}

void insert(int begin, int end, int i)
{
	if (segmenttree[i].begin==begin && segmenttree[i].end==end)
	{
		segmenttree[i].cover++;
		if (segmenttree[i].add) res--; // 如果曾经分裂过, 则多加的无效
		return;
	}
	int mid = getmid(i); 
	if (mid>=end) insert(begin, end, i<<1); 
	else if (mid<begin) insert(begin, end, (i<<1)+1);
	else
	{
		if (!segmenttree[i].cover&&!segmenttree[i].add) // 如果未曾被覆盖过并且尚未分裂过
		{
			segmenttree[i].add = true;
			res++;
		}
		insert(begin, mid, i<<1);
		insert(mid+1, end, (i<<1)+1);
	}
}

int gettot(int root) // 获取root为根的线段树覆盖的总长度
{
	if (segmenttree[root].end==segmenttree[root].begin) return 0; // 如果是叶子节点的话, 则返回0
	return segmenttree[root].cover?segmenttree[root].end-segmenttree[root].begin:gettot(root<<1)+gettot((root<<1)+1); // 如果不是叶子而且整棵树都被覆盖了的话，则直接返回该节点代表线段的总长度,否则递归考察
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int begin[10] = {7 ,3, 8, 5, 6 ,11, 4 ,9 ,10, 2}, end[10]={8, 5 ,12, 6 ,9 ,15 ,7 ,10, 13, 3};
	build(2, 15, 1);
	for (int i = 0; i<10; i++)
	{
		insert(begin[i], end[i], 1);
	}
	printf("%d\n", gettot(1)+res);
	return 0;
}
/*
测试数据
7 3 8 5 6 11 4 9 10 2
8 5 12 6 9 15 7 10 13 3
*/

注意，板子用的还是【2】中的板子，但是做了改造（【2】中说了，线段树的变化太丰富了~）

其实说来【2】的板子是不适合求线段覆盖长度的. 且看下图

你注意哈，如果我们要求[2,5]的覆盖长度的话，它在加入的过程中会被[1,3]和[4,6]分食掉，但是[3,4]不见了~ 所以我们必须要在分食发生的时候把这个漏掉的长度为1的记上（就是代码中的res）以便最后加上. 但是这样就可以了么? 非也, 因为比如一条线段加入线段树，走到 [a,b]这个线段树的节点的时候，如果刚好和[a,b]一样. 那么就不再往下走，如果之前有线段被[a,b]的孩子节点（比如[a,b]就是[1,6], 孩子就是[1,3]和[4,6]）分食掉的话，则之前因为分食而多加的1其实是不需要加的（因为已经有线段覆盖了这个1了，就不要多加了，这就是代码第38行）. 还有一个地方就是如果多条线段都被[a,b]的孩子节点分食的话，则只加一次，这就是代码第48~49行.

参考

【1】https://yfsyfs.github.io/2019/07/13/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E4%B9%8B%E7%BA%BF%E6%AE%B5%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98/

【2】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91/