题目描述

难度分:$2400$

输入$n(1 \leq n \leq 10^5)$和一个$1$~$n$的排列$a$。

$a$有$\frac{n(n+1)}{2}$个非空连续子数组，从中（等概率的）随机选一个子数组$b$。

设$b$的长度为$k$，那么$b$一共有$k!$种不同的排列，从中（等概率的）随机选一个，替换掉$a$中的子数组$b$。

输出替换后，$a$的逆序对的期望值。与答案的误差不能超过$10^{-9}$。

输入样例

3
2 3 1

输出样例

1.916666666666666666666666666667

算法

数学+树状数组

这道题的难度主要在于数学推导，数据结构的使用其实很简单。不妨设$i \lt j$，分为以下两种情况考虑贡献：

1. $a[i] \gt a[j]$，则如果选择的区间包含$[i,j]$这个子数组，就会有$\frac{1}{2}$的概率使得这个逆序对被破坏掉。要涵盖$[i,j]$这个区间，则区间左端点可以是$[1,i]$，区间右端点可以是$[j,n]$，而事件全集的数量为$\frac{n(n+1)}{2}$（左端点有$n$种选择，而右端点大于等于左端点），选择的区间覆盖住$[i,j]$的概率为$\frac{i \times (n-j+1)}{\frac{(1+n)n}{2}}$。一旦对这个涵盖子数组$[i,j]$的区间进行打乱，就有$\frac{1}{2}$的概率将这个逆序对破坏掉，因此有负贡献$\frac{i \times (n-j+1)}{(1+n)n}$。
2. $a[i] \lt a[j]$，同理则有正贡献$\frac{i \times (n-j+1)}{(1+n)n}$。

可以用树状数组统计$1$到$i$内的下标之和，用原始的逆序对数减去总贡献就是答案。

复杂度分析

时间复杂度

遍历一遍数组$a$就能求得答案，而对于每个$a[i]$，需要进行树状数组的修改和查询操作，时间复杂度都是$O(log_2n)$的，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的原数组$a$，空间消耗主要就在于树状数组，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N];

class Fenwick {
public:
    explicit Fenwick(int n): sums_(n + 1) {}

    int lowbit(int x) {
        return x&-x;
    }

    void add(int idx, int val) {
        for(; idx <= n; idx += lowbit(idx)) {
            sums_[idx] += val;
        }
    }

    LL query(int idx) {
        LL ans = 0;
        for(; idx > 0; idx -= lowbit(idx)) {
            ans += sums_[idx];
        }
        return ans;
    }

    LL query(int left, int right) {
        return query(right) - query(left - 1);
    }

    LL operator[](int x) {
        return query(x);
    }

private:
    vector<LL> sums_;
};

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    Fenwick btree(n), ctree(n);
    double res = 0, tot = 0;
    for(int i = 1; i <= n; i++) {
        tot += ctree[n] - ctree[a[i]];
        ctree.add(a[i], 1);
        res += (n - i + 1) * (btree[n] - btree[a[i]]);
        res -= (n - i + 1) * btree[a[i]];
        btree.add(a[i], i);
    }
    res /= n;
    res /= n + 1;
    printf("%.10lf", tot - res);
    return 0;
}