题目详情题解（0）讨论（0）提交记录（0）

AT_abc273_c.[ABC273C] (K+1)-th Largest Number

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的数列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)。对于 K=0,1,2,…,N−1K = 0, 1, 2, \ldots, N-1 的每一个 KK，请解决以下问题：

求满足下列条件的 11 到 NN 之间的整数 ii 的个数。

  • 在 AA 中，比 AiA_i 大的整数恰好有 KK 种。

输入格式

输入以如下格式从标准输入读入。

NN A1A_1 A2A_2 …\ldots ANA_N

输出格式

请输出 NN 行。对于 i=1,2,…,Ni = 1, 2, \ldots, N，第 ii 行输出当 K=i−1K = i-1 时问题的答案。

输入输出样例

  • 输入#1

    6
2 7 1 8 2 8

    输出#1

    2
1
2
1
0
0

  • 输入#2

    1
1

    输出#2

    1

  • 输入#3

    10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

    输出#3

    2
1
2
1
2
1
1
0
0
0

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 输入均为整数

样例解释 1

以 K=2K = 2 为例，问题的答案如下计算：

  • 对于 A1=2A_1 = 2，在 AA 中比 A1A_1 大的整数有 7,87, 8 共 22 种。
  • 对于 A2=7A_2 = 7，在 AA 中比 A2A_2 大的整数有 88 共 11 种。
  • 对于 A3=1A_3 = 1，在 AA 中比 A3A_3 大的整数有 2,7,82, 7, 8 共 33 种。
  • 对于 A4=8A_4 = 8，在 AA 中比 A4A_4 大的整数有 00 种（不存在）。
  • 对于 A5=2A_5 = 2，在 AA 中比 A5A_5 大的整数有 7,87, 8 共 22 种。
  • 对于 A6=8A_6 = 8，在 AA 中比 A6A_6 大的整数有 00 种（不存在）。

因此，在 AA 中比 AiA_i 大的整数恰好有 K=2K = 2 种的 ii 有 i=1i = 1 和 i=5i = 5，共 22 个。所以 K=2K = 2 时的答案为 22。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页