想要更好的阅读体验？

T2

题意:给一个排列$p$,要支持两种操作:

• 交换$x,x+1$
• 询问$k$次冒泡排序之后的逆序对数

$n,m\le 2\times 10^5,k\le 2^{30}$

两个性质:

• $n$次冒泡之后数列有序,不存在逆序对

• 记$inv(i)=\sum_{j\lt i}[p_j\gt p_i]$,则$k$次冒泡之后

$$ \sum inv’(i)=\sum max(inv(i)-k,0) $$

BIT预处理一下$inv$,然后两个BIT维护就好.
修改的时候只影响两个位置,BIT上直接搞.
时间复杂度:$O((n+m)\log n)$

code