113 lines
1.6 KiB
Markdown
113 lines
1.6 KiB
Markdown
# 冒泡排序
|
||
|
||
## 题目背景
|
||
|
||
对于一个排列 $a[1...n]$，进行一趟冒泡排序的代码为：
|
||
```cpp
|
||
for(int i=1;i<n;++i){
|
||
if(a[i]>a[i+1]) swap(a[i], a[i+1]);
|
||
}
|
||
```
|
||
在进行 $n-1$ 趟冒泡排序之后，数组变为有序。
|
||
|
||
## 题目描述
|
||
|
||
给一个长度为 $n$ 的排列 $a[1...n]$ 和 $q$ 次询问，每次询问形如 $(k,x)$：代表询问 $x$ 这个数在 $k$ 趟排序之后的位置下标。
|
||
|
||
## 输入格式
|
||
|
||
第一行1个整数 $n$
|
||
|
||
第二行 $n$ 个整数 $a[1...n]$，保证是一个排列
|
||
|
||
第三行1个整数 $q$
|
||
|
||
接下来 $q$ 行，每行2个整数 $(k,x)$ 代表一次询问
|
||
|
||
## 输出格式
|
||
|
||
输出 $q$ 行，每行1个整数代表答案
|
||
|
||
## 样例 #1
|
||
|
||
### 样例输入 #1
|
||
|
||
```
|
||
5
|
||
4 3 5 1 2
|
||
3
|
||
2 1
|
||
4 4
|
||
1 5
|
||
```
|
||
|
||
### 样例输出 #1
|
||
|
||
```
|
||
2
|
||
4
|
||
5
|
||
```
|
||
|
||
## 样例 #2
|
||
|
||
### 样例输入 #2
|
||
|
||
```
|
||
5
|
||
4 5 2 3 1
|
||
5
|
||
3 1
|
||
4 2
|
||
3 3
|
||
2 4
|
||
1 5
|
||
```
|
||
|
||
### 样例输出 #2
|
||
|
||
```
|
||
2
|
||
2
|
||
3
|
||
4
|
||
5
|
||
```
|
||
|
||
## 样例 #3
|
||
|
||
### 样例输入 #3
|
||
|
||
```
|
||
见下发样例
|
||
```
|
||
|
||
### 样例输出 #3
|
||
|
||
```
|
||
|
||
```
|
||
|
||
## 提示
|
||
|
||
【样例1解释】
|
||
|
||
第1趟排序之后数组变为 $[3,4,1,2,5]$
|
||
|
||
第2趟排序之后数组变为 $[3,1,2,4,5]$
|
||
|
||
第3趟排序之后数组变为 $[1,2,3,4,5]$
|
||
|
||
【数据范围】
|
||
|
||
对于20%的数据，$n,q\le 2000$。
|
||
|
||
对于另20%的数据，$n,q\le 10^5$，不同的 $k$ 取值不超过20种。
|
||
|
||
对于另20%的数据，$n,q\le 10^5$，不同的 $x$ 取值不超过20种。
|
||
|
||
对于另20%的数据，$n,q\le 10^5$。
|
||
|
||
对于100%的数据，$1\le n,q \le 5\times 10^5, 1\le k<n, 1\le x\le n$，$a[1...n]$ 保证是一个排列。
|
||
|
||
注意输入输出量较大，请使用快速的读写方式。 |