问题 4742 --冒泡排序(本站数据)

4742: 冒泡排序(本站数据)

题目描述

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

输出

输出到文件 bubble.out 中。
对于每次询问操作输出一行一个整数表示答案。

样例输入输出

输入#1 复制
3 6
1 2 3
2 0
1 1
1 2
2 0
2 1
2 2
输出#1 复制
0
2
1
0

提示

【样例1解释】
第一次操作:排列为 $\{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 2$:$n , m \le 100$。 
对于测试点 $3 \sim 4$:$n , m \le 2,000$。 
对于测试点 $5 \sim 6$:交换操作个数不超过 $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}$。

序号 标题 作者 发表时间 费用 订购数 操作