CF351B Jeff and Furik
有一个长度为n的排列p,Jeff每次操作选两个相邻元素交换，Furik每次操作随机执行下列操作之一：
1.对于所有p[i]<p[i+1],随机取一对p[i]与p[i+1]交换
2.对于所有p[i]>p[i+1],随机取一对p[i]与p[i+1]交换两个操作被选中的概率均为0.5。如果一个操作无法进行，那么furik必定会进行可以进行的操作。
两人轮流操作，Jeff先手。当排列为升序时，游戏结束。 Jeff希望游戏尽早结束，那么在Jeff每次操作最优的情况下，游戏结束时两人操作次数的期望值是多少？。
换个角度思考问题。题目的目的即是使得这个排列的逆序对数量变为 \(0\) 且操作数量最少。
可以发现 Jeff 每次操作可以减少一个逆序对。
Furik 操作，有 \(0.5\) 的概率增加一个逆序对，\(0.5\) 的概率减少一个逆序对。所以每操作两次，有 \(0.5\) 的概率减少两个逆序对，\(0.5\) 的概率逆序对数量不变。也就说每 \(2\) 次操作逆序对期望减少 \(1\) 个。
因为他俩的操作也分先后，所以奇偶分类讨论一下，假设逆序对有 \(x\) 个：
- 奇数个逆序对，操作次数为 \(2x-1\)。
- 偶数个逆序对，操作次数为 \(2x\)。
统计逆序对树状数组即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=500005;
int n,a[N],cnt;
struct BIT{
int c[N];
inline int lowbit(int x){return x&-x;}
inline void update(int i,int v){for(;i<=n;i+=lowbit(i))c[i]+=v;}
inline int getsum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=c[i];return ans;}
}c;
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=n;i>=1;--i){
cnt+=c.getsum(a[i]);
c.update(a[i],1);
}
if(cnt&1){printf("%.6lf\n",2.0*cnt-1.0);}
else printf("%.6lf\n",2.0*cnt);
return 0;
}