解题思路
本题描述了一场积分赛中领先者次数的统计问题。n 名选手初始积分为 0,依次发生 m 次得分事件,每次事件后积分最高的所有选手都算作一次“领先”。暴力模拟总复杂度为 O(n×m),无法通过 n,m≤2×105 的数据。我们采用**相位(phase)**的概念进行优化。
核心思想:
- 定义相位
设当前最高积分值为 C,从 C 开始保持不变,直到某次事件将最高积分提升为 C+1 为止的连续时间段称为一个相位。在同一相位内,最高积分不变,但领先者集合只会增加(每当有选手追平当前最高分时加入),而不会减少;当相位结束时,该相位的领先者集合清空,新的相位开始。