技巧:
差分 => 累加和 => 原数组
累加和 => 差分 => 原数组
思路:
利用差分,范围操作转换成两端操作。
每次在 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) }