4078: 找到第K+1大的数
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## 题目描述
给定一个长度为 $N$ 的序列$ A = (A_1, A_2, \ldots, A_N)$。
对于每个 $K = 0, 1, 2, \ldots, N-1$,求解以下问题:
找出满足以下条件的 $1$ 到 $N$ 之间(含 $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
```
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】
例如,我们将求出 $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$。
【数据范围】
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都是整数
## 题目来源
ABC273C
## 题目背景
K+1)-th Largest Number指的是在一个给定的数组中找到第K+1大的数。也就是说，如果按非递减顺序对数组进行排序，那么第K+1大的数是什么。
举个例子，如果数组是 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]，那么该数组中第4大的数是4。
通常情况下，可以使用一些排序算法，比如快速排序或堆排序，来找到第K+1大的数。另外，也可以使用一些选择算法，比如快速选择算法（Quickselect algorithm），来高效地找到第K+1大的数。