3373. [NOI Online 2020 1st]冒泡排序(民间数据)

现已将@林荫的测试数据与老常的测试数据结合,测试数据更加完善辣!

【题目描述】

数据来源 @林荫 @Mr.Chang

给定一个 $1 \sim 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 \sim 4$：$n , m \le 100$。 

对于测试点 $5 \sim 8$：$n , m \le 2,000$。 

对于测试点 $9 \sim 12$：交换操作个数不超过 $100$。 

对于所有测试点：$2 \le n,m \le 2 × 10^5，t_i \in \{1,2\}，1 \le x \lt n，0 \le k \lt 2^{31}$。

【来源】

NOI Online2020 提高组 第一轮 Task 2