专栏文章

题解：CF749E Inversions After Shuffle

SSunburstFan
CF749E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipz3xox
此快照首次捕获于
2025/12/03 20:18
3 个月前
此快照最后确认于
2025/12/03 20:18
3 个月前
查看原文

CF749E Inversions After Shuffle

题目大意

给定一个排列，随机打乱其中一部分，求期望的逆序对个数。

解题思路

考虑对于一个数对 (ai,aj),i<j(a_i,a_j),i<j，
如果 (ai,aj)(a_i,a_j) 被包含在打乱的区间中，则会产生一半的正贡献或一半的负贡献。
(ai,aj)(a_i,a_j) 被包含在打乱的区间中的概率为：i×(n−j+1)12×n×(n+1)=2×i×(n−j+1)n×(n+1)\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)}
那么：
ai>aja_i>a_j，则减少的逆序对个数增加 12×2×i×(n−j+1)n×(n+1)=i×(n−j+1)n×(n+1)\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)}。
同理，ai<aja_i<a_j，则减少的逆序对个数减少 12×2×i×(n−j+1)n×(n+1)=i×(n−j+1)n×(n+1)\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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...