「求swap(a[l],a[r])，逆序对变化量」

求swap(a[l],a[r])，逆序对变化量

被骇客银狼阻止的越权访问保存失败

求swap(a[l],a[r])，逆序对变化量

_8008008楼主2024/10/9 20:55

设一有 $n$ 个元素的序列，有 $w_1$ 个逆序对。
现有 $1\le l<r\le n$ ，swap $(a_l,a_r)$ ，现在逆序对数量为 $w_2$
怎么 $O(n)$ 求 $\Delta=w_2-w_1$

2024/10/9 20:55