#NC16649. 校门外的树

校门外的树

题目描述

某校大门外长度为 LL 的马路上有一排树,每两棵相邻的树之间的间隔都是 11 米。我们可以把马路看成一个数轴,马路的一端在数轴 00 的位置,另一端在 LL 的位置;数轴上的每个整数点,即 0,1,2,…,L0,1,2,\ldots,L,都种有一棵树。

由于马路上有一些区域要用来建地铁,这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。请你计算将这些树都移走后,马路上还有多少棵树。

输入格式

第一行输入两个整数 L,ML,M,用空格隔开,表示马路的长度和地铁施工区域数。已有本地输入校验范围为 1≤L≤100001\le L\le10000,1≤M≤1001\le M\le100。

接下来 MM 行,每行输入两个整数 ui,viu_i,v_i,用空格隔开,表示第 ii 个施工区域的起始点和终止点的坐标,满足 0≤ui≤vi≤L0\le u_i\le v_i\le L。

输出格式

输出一个整数,表示移除所有施工区域内(包括端点)树后,剩余的树的总棵树数。

提示

马路上共有 501501 棵树。施工区域 [150,300] 中含有 151151 棵,[100,200] 中含有 101101 棵,[470,471] 中含有 22 棵。三个区域的重叠部分 [150,200] 有 5151 棵被重复移除,所以实际移除的树数为 151+101+2−51=203151+101+2-51=203,因此剩余 501−203=298501-203=298 棵。

样例 1

500 3
150 300
100 200
470 471
298

来源

牛客原题