CF_#388(Div. 2)_E

题目传送门
题意略、
首先,我们可以发现,每对数对答案的贡献是独立的,于是,我们先考虑第$i$个数和第$j$个数对答案的贡献$P\left ( i,j \right )$(下标从$1$开始):
可以,算出,包含$i$和$j$的区间个数为$i\left ( n - j + 1 \right )$个,对于每个区间,我们可以发现第$i$个数在第$j$个数前面的概率和第$i$个数在第$j$个数后面的概率是相同的,都是$\frac{1}{2}$(原因想想就知道了)。当选择的区间没有同时包含$i$和$j$时,其贡献为$\left[ a_i > a_j \right]$
所以,我们就能得到
$P\left ( i,j \right )= \left ( 1 - \frac{2i\left ( n - j + 1 \right )}{n\left ( n + 1 \right )}\right )\left [ a_{i}> a_{j} \right ] + \frac{i\left ( n - j + 1 \right )}{n\left ( n + 1 \right )}$
所以,最后的答案就是
$$\sum_{i = 1}^{n -1}\sum_{j = i + 1}^{n}\left ( 1 - \frac{2i\left ( n - j + 1 \right )}{n\left ( n + 1 \right )}\right )\left [ a_{i}> a_{j} \right ] + \frac{i\left ( n - j + 1 \right )}{n\left ( n + 1 \right )}$$
当然,我们肯定不能暴力枚举每一对$i$和$j$,但是,我们把上式变形一下,然后化简,就可以得到
$$\sum_{i = 1}^{n - 1}\left ( \frac{i\left ( n - i \right )\left ( n - i + 1 \right )}{2n\left ( n + 1 \right )} + \sum_{j = i + 1}^{n}\left [ a_{i} > a_{j} \right ] + \frac{2i}{n\left ( n + 1 \right )} \sum_{j = i + 1}^{n}\left ( n - j + 1 \right )\left [ a_{i}> a_{j} \right ] \right )$$
右边的两个和式一个就是求逆序数个数,另一个就是求逆序数的下标和,显然都可以在$nlogn$的时间维护出来
所以……就做出来啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//created by missever
#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const int maxn = 100005;
LL sum[maxn * 4];
int num[maxn * 4];
int a[maxn],n;
void add(int t,int l,int r,int x)
{
if(l == r)
{
num[t]++;
sum[t] += n - x + 1;
return;
}
int mid = (l + r) >> 1;
if(a[x] <= mid) add(t<<1,l,mid,x);
else add(t<<1|1,mid + 1,r,x);
num[t]++;
sum[t] += n - x + 1;
}
P query(int t,int l,int r,int x)
{
if(r <= a[x]) return P(sum[t],num[t]);
int mid = (l + r) >> 1;
if(a[x] <= mid) return query(t<<1,l,mid,x);
else
{
P u,v;
u = query(t<<1,l,mid,x);
v = query(t<<1|1,mid + 1,r,x);
return P(u.first + v.first,u.second + v.second);
}
}
int main(){
int i;
P u;
LL f = 0,e = 0;
long double ans;
scanf("%d",&n);
for(i = 1;i <= n; i++) scanf("%d",&a[i]);
add(1,1,n,n);
for(i = n - 1;i > 0; i--)
{
e += 1LL * (n - i) * (n - i + 1) / 2 * i;
u = query(1,1,n,i);
e -= u.first * i * 2LL;
f += u.second;
add(1,1,n,i);
}
ans = 1.0 * e / (1LL * n * (n + 1)) + f;
printf("%.10f\n",(double)ans);
return 0;
}

后记:
使用下标要加斜杠,不然显示不出来
大括号……也有问题,还是别用了
结论:GFM并不是标准的markdown