题解区都是 O(nlogn)O(n \log n)O(nlogn) 算法,但显然有一个更优的 O(n)O(n)O(n) 算法,发不了题解了,在这里简要写一下:
考虑以下算法:
注意到若某个非 iii 的人 jjj 满足 sj∈[si,ti]s_j \in[s_i,t_i]sj∈[si,ti],则 jjj 会向 iii 问好。
应此只要求出关于前 iii 秒到达人数的前缀和 aia_iai, 则答案便是 ati−asi−1−1a_{t_i}-a_{s_i-1}-1ati−asi−1−1。
代码长度也远低于题解,不卡常轻松最优解。