题解

• 题意简述：有 $n$ 位领导，按顺序收到 $m$ 张匿名投票；在每次投票后，所有当前票数等于全体最高票数的领导都算“领先一次”。输出每位领导的领先次数。

• 核心思路：

  • 定义“相位”为当前最高票数为某个固定值 $c$ 的连续时间段；当某人把最高票从 $c$ 提升到 $c+1$ 时，相位切换。
  • 在同一相位内，领先集合 $S$ 只会“加入”而不会“删除”（直到相位结束统一重置）。
  • 线性扫描投票，维护全局时间 $t$（已处理投票数）；当某领导在相位 $p$ 中“加入 $S$”时记录一次事件 $(p, t)$；相位 $p$ 的结束时刻为 $T_p$。
  • 该领导在相位 $p$ 的贡献即 $T_p - t$。把所有加入事件的贡献求和即为答案。
  • 每次投票至多产生一次“加入事件”，相位总数至多为 $m$，因此总复杂度 $O(m)$，空间 $O(n+m)$。

• 正确性要点：相位内 $S$ 单调只增，统一在相位末尾结算；对每个“加入”只需在相位结束用 $T_p - t$ 计入即可，无需逐步对 $S$ 中所有人逐次加 $1$。

• 复杂度：时间 $O(m)$，空间 $O(n+m)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> cnt(n + 1, 0);        // 每个领导当前票数
    vector<long long> ans(n + 1, 0);  // 每个领导领先次数
    vector<vector<pair<int,int>>> joins(n + 1); // 加入事件：(phase_id, join_time)

    int maxCnt = 0;   // 当前最高票数
    int phaseId = 0;  // 当前相位编号（从1开始）
    int t = 0;        // 已处理投票数（时间）
    vector<int> phaseEnd(1, 0); // 相位结束时刻，phaseEnd[phaseId]，下标0占位

    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        cnt[x]++;

        if (cnt[x] == maxCnt + 1) {
            // 最高票数提升 -> 旧相位结束，新相位开始
            if (phaseId > 0) phaseEnd[phaseId] = t;
            phaseId++;
            if ((int)phaseEnd.size() <= phaseId) phaseEnd.push_back(0);
            maxCnt++;
            // 新相位中，x 作为第一个领先者在时刻 t 加入
            joins[x].push_back({phaseId, t});
        } else if (cnt[x] == maxCnt) {
            // 在当前相位追平最高票，时刻 t 加入
            joins[x].push_back({phaseId, t});
        }
        // 完成本次投票，时间前进
        t++;
    }
    if (phaseId > 0) phaseEnd[phaseId] = t; // 最后相位结束时间

    // 汇总答案：每次加入贡献为 (相位结束时间 - 加入时间)
    for (int i = 1; i <= n; i++) {
        for (auto &e : joins[i]) {
            int pid = e.first, join_t = e.second;
            ans[i] += (long long)phaseEnd[pid] - join_t;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

Python

import sys

data = sys.stdin.read().strip().split()
n, m = map(int, data[:2])
votes = list(map(int, data[2:2+m]))

cnt = [0] * (n + 1)         # 每个领导当前票数
ans = [0] * (n + 1)         # 每个领导领先次数
joins = [[] for _ in range(n + 1)]  # 每位领导的加入事件：(phase_id, join_time)

max_cnt = 0     # 当前最高票
phase_id = 0    # 相位编号（从1开始）
t = 0           # 已处理投票数（时间）
phase_end = [0] # 相位结束时间，索引0占位

for x in votes:
    cnt[x] += 1
    if cnt[x] == max_cnt + 1:
        # 相位切换
        if phase_id > 0:
            phase_end[phase_id] = t
        phase_id += 1
        if len(phase_end) <= phase_id:
            phase_end.append(0)
        max_cnt += 1
        joins[x].append((phase_id, t))  # 新相位首个领先者
    elif cnt[x] == max_cnt:
        joins[x].append((phase_id, t))  # 追平加入
    t += 1

if phase_id > 0:
    phase_end[phase_id] = t

for i in range(1, n + 1):
    total = 0
    for pid, jt in joins[i]:
        total += phase_end[pid] - jt
    ans[i] = total

print(' '.join(str(ans[i]) for i in range(1, n + 1)))

Java

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        BufferedInputStream in = new BufferedInputStream(System.in);
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;
        int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt(), m = fs.nextInt();

        int[] cnt = new int[n + 1];          // 每个领导当前票数
        long[] ans = new long[n + 1];        // 每个领导领先次数
        @SuppressWarnings("unchecked")
        ArrayList<int[]>[] joins = new ArrayList[n + 1]; // 每位领导加入事件：(phase_id, join_time)
        for (int i = 1; i <= n; i++) joins[i] = new ArrayList<>();

        int maxCnt = 0;   // 当前最高票
        int phaseId = 0;  // 相位编号（从1开始）
        int t = 0;        // 已处理投票数（时间）
        int[] phaseEnd = new int[m + 2]; // 相位结束时间，最多 m 个相位

        for (int i = 0; i < m; i++) {
            int x = fs.nextInt();
            cnt[x]++;

            if (cnt[x] == maxCnt + 1) {
                // 相位切换
                if (phaseId > 0) phaseEnd[phaseId] = t;
                phaseId++;
                maxCnt++;
                joins[x].add(new int[]{phaseId, t}); // 新相位首个领先者
            } else if (cnt[x] == maxCnt) {
                joins[x].add(new int[]{phaseId, t}); // 追平加入
            }
            t++;
        }
        if (phaseId > 0) phaseEnd[phaseId] = t;

        for (int i = 1; i <= n; i++) {
            long total = 0;
            for (int[] e : joins[i]) {
                int pid = e[0], jt = e[1];
                total += (long) (phaseEnd[pid] - jt);
            }
            ans[i] = total;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb);
    }
}

题目内容

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

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

输入描述

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

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

输出描述

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

样例1

输入

5 5
1 2 3 4 4

输出

4 3 2 2 0

说明

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