题目链接

https://codeforces.com/problemset/problem/351/B

题目大意

给你一个1到n的排列a[i]。
Jeff和Furik轮流操作，Jeff先手。
Jeff每次会交换a[i]>a[i+1]的两个数。
Furik每次有1/2的概率交换a[i]<a[i+1]的两个数，有1/2的概率交换a[i]>a[i+1]的两个数。
当这个排列变成升序时，游戏停止。
问你操作数的期望。

解题思路

假设原序列中有t个逆序对。
那么将这个序列变成升序，就是将这t个逆序对一个个消除。
　　
Jeff每次会减少一个逆序对。
Furik每次有1/2概率增加一个逆序对，有1/2概率减少一个逆序对。
加起来就是：每两次操作，有1/2概率减少两个逆序对，有1/2概率不变。
也就是：每两次操作，一定会减少一个逆序对。（只考虑数学期望的话）
　　
然而在最后一个回合中，有可能Jeff操作完后，游戏就已经结束了，不用Furik再操作。
当且仅当逆序对个数t为奇数时，上面的情况成立，操作数-1。
所以最终答案为：t*2 - (t&1)
题解来自
逆序对的三种求法
本题好像也可以n^2暴力求逆序对。

AC代码

//注释部分为进行离散化的代码
#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int ans,n,c[N],p[N];
/*
struct node{
    int v,idx,pos;
};
node p[N];
bool cmp1(node a,node b){
    return a.v<b.v;
}
bool cmp2(node a,node b){
    return a.idx<b.idx;
}
*/
int lowbit(int x){
    return x&(-x);
}
int getsum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int x,int add){
    while(x<=n){
        c[x]+=add;
        x+=lowbit(x);
    }
}
int main(){
    cin>>n;
    /*
    for(int i=1;i<=n;i++){
        cin>>p[i].v;
        p[i].idx=i;
        update(p[i],1);
        ans+=i-getsum(p[i]);
    }
    sort(p+1,p+n+1,cmp1);
    for(int i=1;i<=n;i++) p[i].pos=i;
    sort(p+1,p+n+1,cmp2);
    for(int i=1;i<=n;i++){
        update(p[i].pos,1);
        ans+=i-getsum(p[i].pos);
    }
    */
    for(int i=1;i<=n;i++){
        cin>>p[i];
        update(p[i],1);
        ans+=i-getsum(p[i]);
    }
    ans=2*ans-(ans&1);
    printf("%.6lf\n",(double)ans);
} 

哔哔赖赖

没想到，时隔俩月，我居然还能大差不差的写出树状数组求逆序对，爱了！
但是这道题我不会啊！！！一看到求期望瞬间懵了！