本题描述了一场积分赛中领先者次数的统计问题。n 名选手初始积分为 0,依次发生 m 次得分事件,每次事件后积分最高的所有选手都算作一次“领先”。暴力模拟总复杂度为 O(n×m),无法通过 n,m≤2×105 的数据。我们采用**相位(phase)**的概念进行优化。
核心思想:
在一场积分赛中,有 n 名选手,编号为 1∼n,初始积分均为 0。接下来依次发生 m 次得分事件,每次事件有一名选手获得 1 积分。每次事件后,积分最高的选手被称为当前领先者;若有多名选手积分相同且均为最高,则他们都视为当前领先者。请你计算每位选手在整个过程中成为当前领先者的次数。
选手人数 n 和得分事件数 m 满足 1≤n,m≤2×105。每次得分事件中获分的选手编号 pi 满足 1≤pi≤n。
第一行包含两个整数 n 和 m。 第二行包含 m 个整数 p1,p2,…,pm(1≤pi≤n),依次表示每次得分事件中获分的选手编号。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册