#1454. CSP-模拟赛001-T2
CSP-模拟赛001-T2
题目描述
有以下排序算法,可将数组 中的元素从小到大排序:
for (int i = 1; i <= n; i++) {
for (int j = i; j >= 2; j--) {
if (a[j] < a[j-1]) {
int t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
现有一长度为 的数组 ,编号从 开始,数组中的元素均为 int
范围内自然数。
对数组做如下 次操作:
- 操作:输入
1 i x
,将 的第 个元素,即a[i]
的值,修改为 。数据保证 ,。注意:该操作修改的值会保留,即会影响后续的操作。 - 操作:输入
2 i
,将 数组 按照上面的代码进行排序,然后输出原数组 的第 个元素,即a[i]
在排序后的新数组中的下标。数据保证 。注意:该操作不会修改原数组,排序后的数组不会被保留,即不影响后续的操作。
数据保证操作 的次数不超过 。
输入格式
第一行,为两个正整数 ,即数组长度与操作次数。
第二行,为 个自然数,即原数组 的元素,空格隔开
接下来 行,每行 至 个正整数,表示一次操作。
输出格式
针对每次个操作 的询问,输出一行答案。
样例 #1
样例输入 #1
3 5
3 2 1
2 3
1 3 2
2 2
1 2 3
2 2
样例输出 #1
1
1
3
提示
【数据范围】
对于所有测试数据,满足 ,,,。
对于所有测试数据,保证最多有 次操作。
相关
在下列比赛中: