线段树练习题一【线段树】

线段树练习题一【线段树】"/>

线段树练习题一【线段树】

>Description
桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

>Input
第一行输入一个整数n，表示桌面总宽度
第二行输入一个整数m，表示盒子数量
接下来m行，每行输入两个数x,y，表示第i个盒子的起始位置和终止位置

>Output
阴影宽度

>Sample Input
20
4
1 5
3 8
7 10
13 19

>Sample Output
15

>解题思路

离散化做法
这道题可以用离散化做，但是离散化做会很慢，所以安利线段树做法。

一道线段树模板题，记录每个盒子的阴影时直接记录，如果当前节点已经是阴影了的话就直接return，到达寻找的节点时把节点标记为1。
查找也是直接查找1~n，遇到一个节点如果已经标记为1的话就直接返回该节点的区间长度，否则一直搜到叶子节点。

查找这里有个地方很奇怪，搞得我样例一直没对，后来我手动模拟的时候才发现：如果遇到阴影的区间与上一次遇到的相连了，就返回 r − l + 1 r-l+1 r−l+1，否则返回 r − l r-l r−l。

>代码

#include <iostream>
#include <cstdio>using namespace std;int n, m, a, b, f, t[400005];void insert (int d, int l, int r, int lf, int rf) //编号为d的节点，区间为l~r，查找lf~rf
{if (t[d] == 1) return; //如果当前节点已经全部标记过了就不用往下搜了if (l == lf && r == rf){t[d] = 1; //标记return;}int mid = (l + r) >> 1;if (lf <= mid) insert (d * 2, l, mid, lf, min (mid, rf));if (rf > mid) insert (d * 2 + 1, mid + 1, r, max (mid + 1, lf), rf);
}
int find (int d, int l, int r) //编号为d的节点，区间为l~r
{if (t[d] == 1){int sum = r - l;if (l == f + 1) sum++;f = r; //f记录上一块阴影在哪里结束，见题解return sum;}if (l == r) return 0;int mid = (l + r) >> 1;return find (d * 2, l, mid) + find (d * 2 + 1, mid + 1, r);
}
int main()
{f = -2;scanf ("%d%d", &n, &m);for (int i = 1; i <= m ; i++){scanf ("%d%d", &a, &b);insert (1, 1, n, a, b);}printf ("%d", find (1, 1, n));return 0;
}