题目描述
难度分:$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$,分为以下两种情况考虑贡献:
- $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}$。
- $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;
}