102732: [AtCoder]ABC273 C - (K+1)-th Largest Number

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $300$ points

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$. For each $K = 0, 1, 2, \ldots, N-1$, solve the following problem.

Find the number of integers $i$ between $1$ and $N$ (inclusive) such that:

  • $A$ contains exactly $K$ distinct integers greater than $A_i$.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $N$ lines. For $i = 1, 2, \ldots, N$, the $i$-th line should contain the answer for $K = i-1$.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for $K=2$.

  • Regarding $A_1 = 2$, $A$ contains $2$ distinct integers greater than $A_1$: $7$ and $8$.
  • Regarding $A_2 = 7$, $A$ contains $1$ distinct integer greater than $A_2$: $8$.
  • Regarding $A_3 = 1$, $A$ contains $3$ distinct integers greater than $A_3$: $2, 7$, and $8$.
  • Regarding $A_4 = 8$, $A$ contains $0$ distinct integers greater than $A_4$ (there is no such integer).
  • Regarding $A_5 = 2$, $A$ contains $2$ distinct integers greater than $A_5$: $7$ and $8$.
  • Regarding $A_6 = 8$, $A$ contains $0$ distinct integers greater than $A_6$ (there is no such integer).

Thus, there are two $i$'s, $i = 1$ and $i = 5$, such that $A$ contains exactly $K = 2$ distinct integers greater than $A_i$. Therefore, the answer for $K = 2$ is $2$.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Input

题意翻译

你有一个序列 $A = (A_1, A_2 , \ ..., A_n)$ 你需要求有多少个数满足 $A$ 中有 $k$ 个不同的数 $\geq$ $a_i$ $(i \in [1, n])$

Output

分数：300分

问题描述

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

找出介于 1 和 $N$（含）之间的整数 $i$ 的数量，使得：

  • $A$ 包含恰好 $K$ 个大于 $A_i$ 的不同整数。

约束条件

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

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

输出

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

样例输入 1

6
2 7 1 8 2 8

样例输出 1

2
1
2
1
0
0

例如，我们将找到答案为 $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$。

样例输入 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

Source/Category

加入题单

上一题 下一题 算法标签：