线段树练习题一【离散化】

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

线段树练习题一【离散化】

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

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

>Output
阴影宽度

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

>Sample Output
15

>解题思路

离散化模板。

>代码

#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;struct box
{int x, y;
} a[100005];
int l, n, ans, b[200005];int main()
{scanf ("%d%d", &l, &n);for (int i = 1; i <= n; i++){scanf ("%d%d", &a[i].x, &a[i].y); //原数组b[i] = a[i].x; b[n + i] = a[i].y; //离散数组}sort (b + 1, b + 1 + 2 * n); //排序for (int i = 2; i <= 2 * n; i++) //扫离散数组for (int j = 1; j <= n; j++) //原数组if (b[i] > a[j].x && b[i] <= a[j].y){ans += b[i] - b[i - 1]; //记录答案break;}printf("%d", ans);return 0;
}