题意简述：有 $n$ 位领导，按顺序收到 $m$ 张匿名投票；在每次投票后，所有当前票数等于全体最高票数的领导都算“领先一次”。输出每位领导的领先次数。
核心思路：
- 定义“相位”为当前最高票数为某个固定值 $c$ 的连续时间段；当某人把最高票从 $c$ 提升到 $c+1$ 时，相位切换。
- 在同一相位内，领先集合 $S$ 只会“加入”而不会“删除”（直到相位结束统一重置）。
- 线性扫描投票，维护全局时间 $t$ （已处理投票数）；当某领导在相位 $p$ 中“加入 $S$ ”时记录一次事件 $(p, t)$ ；相位 $p$ 的结束时刻为 $T_p$ 。

P3558.第2题-最佳领导人投票

1000ms

Difficulty: 5

所属公司 : 阿里

算法与标签>模拟

题目内容

Tk 国这天来到了一年一度的最佳领导人投票环节，总共参与竞选最佳领导人的领导总共有 $n$ 位(编号为 $1$ ~ $n$ )，接下来依次会有 $m$ 名群众按顺序匿名投票，每名群众将会投出自己认为最佳领导人的领导编号。

你身为此次投票的负责人需要记录每名领导有多少次投票后属于票数最多持有者的次数。若有多名领导票数相同且均为最多，则他们均被视为票数最多持有者。

第一行输入两个整数 $n,m(1≤n,m≤2×10^5)$ 表示参与竞选领导个数，投票人数。

第二行输入 $m$ 个整数 $a_i(1 ≤ a_i≤n)$ 表示每位群众支持的领导编号。

输出一行 $n$ 个整数表示每名领导每次投票后属于票数最多持有者的次数，用空格分隔。

输入

5 5
1 2 3 4 4

输出

4 3 2 2 0

说明

编号 $1$ 的领导在前四次投票后都属于领先，编号 $4$ 的领导在第 $4,5$ 次投票后属于领先。

输入

预期输出（选填）