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

题目描述

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

求满足下列条件的 $1$ 到 $N$ 之间的整数 $i$ 的个数。

• 在 $A$ 中，比 $A_i$ 大的整数恰好有 $K$ 种。

输入格式

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

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

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

输入输出样例 #1

输入 #1

6
2 7 1 8 2 8

输出 #1

2
1
2
1
0
0

输入输出样例 #2

输入 #2

1
1

输出 #2

1

输入输出样例 #3

输入 #3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

输出 #3

2
1
2
1
2
1
1
0
0
0

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

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

• 对于 $A_1 = 2$，在 $A$ 中比 $A_1$ 大的整数有 $7, 8$ 共 $2$ 种。
• 对于 $A_2 = 7$，在 $A$ 中比 $A_2$ 大的整数有 $8$ 共 $1$ 种。
• 对于 $A_3 = 1$，在 $A$ 中比 $A_3$ 大的整数有 $2, 7, 8$ 共 $3$ 种。
• 对于 $A_4 = 8$，在 $A$ 中比 $A_4$ 大的整数有 $0$ 种（不存在）。
• 对于 $A_5 = 2$，在 $A$ 中比 $A_5$ 大的整数有 $7, 8$ 共 $2$ 种。
• 对于 $A_6 = 8$，在 $A$ 中比 $A_6$ 大的整数有 $0$ 种（不存在）。

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

由 ChatGPT 4.1 翻译