题目大意

给定一个1到n的排列，然后随机选取一个区间，让这个区间内的数随机改变顺序，问这样的一次操作后，该排列的逆序数的期望是多少

 

首先，一个随机的长度为len的排列的逆序数是(len)*(len-1)/4，这是显然的，因为每种排列倒序一遍就会得到一个新序列，逆序数是len*(len-1)/2 - x（x为原排列的逆序数)

所以我们只需要把所有n*(n-1)/2的区间每种情况都随机化一遍再求逆序对，然后把这个值求和，就可以得到答案了

但是如果用朴素做法，那么复杂度是n^2的

 

考虑dp[x]表示以x为右端点的所有区间的逆序对数

dp[x] = sigma(dp[1~(x-1)]) + f[x]

f[x]表示x这个数对其以x为右端点所有区间的逆序对数所做的贡献，简单说，就是加了x以后，逆序对增加的个数

那么显然出现在第一位的数的贡献为1，而在第二位的数贡献为2，然后把相应的值加到权值线段树里

就可以统计出来所有的dp[x]了

 

最终答案就是 原序列的逆序对数-(Sum(dp[x])-Sum(所有区间随机化))/区间个数

 

PS:精度比较坑，中间整数运算尽量用long long，最后再用long double

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long double ld;const int maxn = 111111;long long tree[maxn*4];void Insert(int o, int l, int r, int k, int v){    if(l == r)    {        tree[o] = v;        return;    }    int mid = (l+r)>>1;    if(k <= mid) Insert(o*2, l, mid, k, v);    else Insert(o*2+1, mid+1, r, k, v);    tree[o] = tree[o*2] + tree[o*2+1];}long long Query(int o, int l, int r, int L, int R){    if(L <= l && r <= R) return tree[o];    int mid = (l+r)>>1;    ld ans = 0;    if(L <= mid) ans += Query(o*2, l, mid, L, R);    if(R > mid) ans += Query(o*2+1, mid+1, r, L, R);    return ans;}int n, x, a[maxn], f[maxn];int main(){    cin>>n;    ld ans = 0;    for(int i = 1; i <= n; i++) cin>>a[i], f[a[i]] = i;    for(int i = 1; i <= n; i++)    {        ans += Query(1, 1, n, a[i], n);        Insert(1, 1, n, a[i], 1);    }    ans *= ((long long)n*(n+1));    memset(tree, 0, sizeof(tree));    long long last = 0;    for(int i = 1; i <= n; i++)    {        ans -= (last + Query(1, 1, n, a[i], n));        last = last + Query(1, 1, n, a[i], n);        Insert(1, 1, n, a[i], f[a[i]]*2);    }    for(int i = 1; i <= n; i++)        ans += ((long long)(n-i+1)*i*(i-1)/2);x`    ans /= ((long long)n*(n+1));    cout<
         
          <
          
           <