CF749E. Inversions After Shuffle

发表于 | 阅读数

给出一个 $1\sim n$ 的排列，从中等概率的选取一个连续段，设其长度为 $l$。对连续段重新进行等概率的全排列，求排列后整个原序列的逆序对的期望个数。

先考虑区间内产生的逆序对

$\sum_{i=1}^n i(i-1)/4\times (n-i+1)$

然后就是其他逆序对就是不会变。
$\sum a_i>a_j/2-i(n-j+1))$

用两个树状数组就好了。

代码 
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
#define mk make_pair
const ll N = 1e6 + 10;
const ll mod = 1e9 + 7;
ll read()
{
    ll x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
double ans;
struct BIT
{
    ll tr[N];
    ll Bmax;
    ll lb(ll x) { return (-x) & x; }
    void init(ll n)
    {
        Bmax = n;
        for (ll i = 0; i <= n; i++)
            tr[i] = 0;
    }
    ll query(ll x)
    {
        if (x <= 0)
            return 0;
        ll res = 0;
        while (x)
        {
            res += tr[x];
            x -= lb(x);
        }
        return res;
    }
    void update(ll x, ll w)
    {
        if (x <= 0)
            return;
        while (x <= Bmax)
        {
            tr[x] += w;
            x += lb(x);
        }
    }
} t1, t2;
int a[N];
int main()
{
    ll n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (ll i = 1; i <= n; i++)
    {
        ans += (double)1.00 * i * (i - 1) / 4.00 * (n - i + 1);
    }

    t1.init(n);
    t2.init(n);
    for (ll i = 1; i <= n; i++)
    {
        ll o1 = t1.query(n) - t1.query(a[i]);
        ll o2 = t2.query(n) - t2.query(a[i]);

        t1.update(a[i], 1);
        t2.update(a[i], i);

        ans += (double)(1.00 * n * (n + 1) * o1 * 0.5 - 1.00 * (n - i + 1) * o2);
    }

    printf("%.10lf", ans / (1.00 * n * (n + 1) / 2));
}