题解：CF749E Inversions After Shuffle
SunburstFan
·
·
题解
CF749E Inversions After Shuffle
题目大意
给定一个排列，随机打乱其中一部分，求期望的逆序对个数。
解题思路
考虑对于一个数对 (a_i,a_j),i<j，
如果 (a_i,a_j) 被包含在打乱的区间中，则会产生一半的正贡献或一半的负贡献。
(a_i,a_j)$ 被包含在打乱的区间中的概率为：$\frac{i\times (n-j+1)}{\frac{1}{2}\times n\times (n+1)} = \frac{2\times i \times (n-j+1)}{n\times (n+1)}
那么：
同理，$a_i<a_j$，则**减少的逆序对个数**减少 $\frac{1}{2}\times \frac{2\times i\times (n-j+1)}{n\times (n+1)} = \frac{i\times (n-j+1)}{n\times (n+1)}$。
可以用树状数组维护，建两颗树状数组，一颗计算原序列逆序对个数，另一颗维护上述的**减少逆序对的个数**，二者相减即可。
这里给出核心代码（树状数组略）：
```cpp
void solve(){
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
Tr1.init(n),Tr2.init(n);
double cnt=0,ans=0;
for(int i=1;i<=n;i++){
cnt+=Tr1(n)-Tr1(a[i]);
Tr1.add(a[i],1);
}
for(int i=1;i<=n;i++){
ans+=(n-i+1)*(Tr2(n)-Tr2(a[i]));
ans-=(n-i+1)*Tr2(a[i]);
Tr2.add(a[i],i);
}
ans/=n*(n+1);
cout<<fixed<<setprecision(12)<<cnt-ans<<endl;
}
```