此题的长明路灯在每一个节日中都被点亮,其实就是每一个节日对应的路灯区间都包含了某一盏路灯,那么该路灯就叫做长明路灯,由于所有节日对应的路灯区间是连续的,所以我们可以直接使用差分来计数每一盏路灯对应了多少个节日,对应的节日数如果为m那么这盏路灯即为长明路灯,对于每一个节日的区间,将该区间内的所有路灯计数加一
#include<iostream>
#include<cstring>
#include<algorithm>
街道上依次排列着 n 盏路灯,编号为 1 到 n。有 m 个节日,第 i 个节日需要点亮编号在 [li,ri] 区间内的所有路灯。
如果一盏路灯在每一个节日中都被点亮,则它被称为“长明路灯”。请你计算长明路灯的数量。
约束条件:路灯的数量 n 和节日的数量 m 均不超过 105,且对于每个节日,有 1≤li≤ri≤n。
第一行包含两个正整数 n 和 m,分别表示路灯的数量和节日的数量。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.