You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $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$。

输出格式

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

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

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}$。