技巧:
差分 => 累加和 => 原数组
累加和 => 差分 => 原数组
思路:
利用差分,范围操作转换成两端操作。
每次在 l r范围内都减去1。相当于 arr[l] -1 arr[r + 1] + 1。
最后累加和还原差分数组, 统计大于0的数量 。
实现: (注意边界 !!!)
package main
import "fmt"
func main() {
var L, M int
fmt.Scan(&L, &M)
// 构建差分数组
delArr := make([]int, L + 1)
delArr[0] = 1
// 范围处理
for i := 0; i < M; i ++ {
var l, r int
fmt.Scan(&l, &r)
delArr[l] -= 1
if r < L {
delArr[r + 1] += 1
}
}
// 累加和恢复数组 并统计
ans,tmp := 0,0
for i := 0; i < L + 1; i++ {
tmp += delArr[i]
if tmp > 0 {
ans ++
}
}
fmt.Println(ans)
} 
京公网安备 11010502036488号