线段树练习题一【线段树】"/>
线段树练习题一【线段树】
>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;
}
更多推荐
线段树练习题一【线段树】
发布评论