[NOI Online 提高组]冒泡排序(民间数据)

题目描述

给定一个 $1 ∼ n$ 的排列 $p_i$,接下来有 $m$ 次操作,操作共两种: 1. 交换操作:给定 $x$,将当前排列中的第 $x$ 个数与第 $x+1$ 个数交换位置。 2. 询问操作:给定 $k$,请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。 对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下: ``` for i = 1 to n-1: if p[i] > p[i + 1]: swap(p[i], p[i + 1]) ```

输入输出格式

输入格式


第一行两个整数 $n$,$m$,表示排列长度与操作个数。 第二行 $n$ 个整数表示排列 $p_i$。 接下来 $m$ 行每行两个整数 $t_i$,$c_i$,描述一次操作: - 若 $t_i=1$,则本次操作是交换操作,$x=c_i$; - 若 $t_i=2$,则本次操作是询问操作,$k=c_i$。

输出格式


对于每次询问操作输出一行一个整数表示答案。

输入输出样例

输入样例 #1

3 6
1 2 3
2 0
1 1
1 2
2 0
2 1
2 2

输出样例 #1

0
2
1
0

说明

#### 样例一解释 第一次操作:排列为 $\{1,2,3\}$,经过 0 轮冒泡排序后为 $\{1,2,3\}$,$0$ 个逆序对。 第二次操作:排列变为 $\{2,1,3\}$。 第三次操作:排列变为 $\{2,3,1\}$。 第四次操作:经过 $0$ 轮冒泡排序后排列变为 $\{2,3,1\}$,$2$ 个逆序对。 第五次操作:经过 $1$ 轮冒泡排序后排列变为 $\{2,1,3\}$,$1$ 个逆序对。 第六次操作:经过 $2$ 轮冒泡排序后排列变为 $\{1,2,3\}$,$0$ 个逆序对。 --- #### 数据范围与提示 对于测试点 1 ∼ 2:$n,m \leq 100$。 对于测试点 3 ∼ 4:$n,m \leq 2000$。 对于测试点 5 ∼ 6:交换操作个数不超过 $100$。 对于所有测试点:$2 \leq n,m \leq 2 \times 10^5$,$t_i \in \{1,2\}$,$1 \leq x < n$,$0 \leq k < 2^{31}$。