(K+1)-th Largest Number

题目描述

你得到一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。 对于每个 $K = 0, 1, 2, \ldots, N-1$，解决以下问题。

找出在 $1$ 到 $N$（含）之间满足以下条件的整数 $i$ 的数量：

$A$ 中恰好有 $K$ 个不同的整数大于 $A_i$。

输入格式

输入按照标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

打印 $N$ 行。 对于 $i = 1, 2, \ldots, N$，第 $i$ 行应包含 $K = i-1$ 的答案。

6
2 7 1 8 2 8

2
1
2
1
0
0

1
1

1

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

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$ 输入中的所有数值均为整数。例如，我们将求 $K=2$ 的答案。

关于 $A_1 = 2$，$A$ 中有 $2$ 个不同的整数大于 $A_1$：$7$ 和 $8$。 关于 $A_2 = 7$，$A$ 中有 $1$ 个不同的整数大于 $A_2$：$8$。 关于 $A_3 = 1$，$A$ 中有 $3$ 个不同的整数大于 $A_3$：$2, 7$，和 $8$。 关于 $A_4 = 8$，$A$ 中有 $0$ 个不同的整数大于 $A_4$（不存在这样的整数）。 关于 $A_5 = 2$，$A$ 中有 $2$ 个不同的整数大于 $A_5$：$7$ 和 $8$。 关于 $A_6 = 8$，$A$ 中有 $0$ 个不同的整数大于 $A_6$（不存在这样的整数）。

因此，有两个 $i$，$i = 1$ 和 $i = 5$，使得 $A$ 中恰好有 $K = 2$ 个不同的整数大于 $A_i$。因此，$K = 2$ 的答案是 $2$。

标签: AtCoder|abc273C

来源

AtCoder|abc273C