#1454. CSP-模拟赛001-T2

CSP-模拟赛001-T2

题目描述

有以下排序算法,可将数组 aa 中的元素从小到大排序:

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;
		}
	}
}

现有一长度为 nn 的数组 aa,编号从 11 开始,数组中的元素均为 int 范围内自然数。

对数组做如下 mm 次操作:

  • 操作11:输入1 i x,将 aa 的第 ii 个元素,即 a[i] 的值,修改为 xx。数据保证 1in1 \le i \le n1x1091 \le x \le 10^9注意:该操作修改的值会保留,即会影响后续的操作
  • 操作22:输入2 i,将 数组 aa 按照上面的代码进行排序,然后输出原数组 aa 的第 ii 个元素,即 a[i] 在排序后的新数组中的下标。数据保证 1in1 \le i \le n注意:该操作不会修改原数组,排序后的数组不会被保留,即不影响后续的操作

数据保证操作 11 的次数不超过 50005000

输入格式

第一行,为两个正整数 n,mn, m,即数组长度与操作次数。

第二行,为 nn 个自然数,即原数组 aa 的元素,空格隔开

接下来 mm 行,每行 2233 个正整数,表示一次操作。

输出格式

针对每次个操作 22 的询问,输出一行答案。

样例 #1

样例输入 #1

3 5
3 2 1
2 3
1 3 2
2 2
1 2 3
2 2

样例输出 #1

1
1
3

提示

【数据范围】

对于所有测试数据,满足 1n80001 \le n \le 80001m2×1051 \le m \le 2 \times {10}^51in1 \le i \le n1x,ai1091 \le x,a_i \le 10^9

对于所有测试数据,保证最多有 50005000 次操作11