Description：

$N$ 个女性和 $M$ 个男性，每个女性指定自己的“如意郎君列表”，用如下算法来为每个女性速配最终接受的男性：将“如意郎君列表”中的男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以 $P$ 的概率接受这个男性。如果她选择了拒绝， $App$ 就会呈现列表中下一个男性。如果列表中所有的男性都已经呈现，那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。两个女性 $a$ 和 $b$ ，如果 $a$ 的编号比 $b$ 的编号小，而 $a$ 选择的男性的编号比 $b$ 选择的编号大，那么女性 $a$ 和女性 $b$ 就叫做一对不稳定因素。求不稳定因素的期望个数。

$1\le N \le5\times 10^5 $

Solution：

若某个男性是某个女性列表中编号第 $k$ 小的，女性列表大小为 $m$ ，则该女性接受该男性的概率为 $\begin{align}(1-P)^{k-1}\times P+(1-P)^{k-1+m}\times P+(1-P)^{k-1+2\times m}\times P+\cdots\cdots\end{align}$

等比数列求和得： $P_k=(1-P)^{k-1}\times P\times \frac {1-[(1-P)^m]^\infty}{1-(1-P)^m}=\frac{(1-P)^{k-1}\times P}{1-(1-P)^m}$

由期望定义得： $$ E(x)=\sum^\infty_{i=1}p_ix_i $$ 逆序对数 $x_i=1$ ，所以： $$ E(x)=\sum^\infty_{i=1}p_i $$ 于是用树状数组维护期望和每次查询后缀和即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

long double p;

vector<int> v[MAXN];

long double c[MAXN];

int lowbit(int x){return x&(-x);}

void add(int p,long double k){for(int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

long double query(int p){long double res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int main()

{

	scanf("%d%d",&n,&m);

	cin >> p;

	int a,b;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&a,&b);

		v[a].push_back(b);

	}

	long double ans = 0;

	for(int i = 1;i <= n;++i)

	{

		sort(v[i].begin(),v[i].end());

		for(int k = 0;k < v[i].size();++k)

		{

			ans += (pow(1 - p,k) * p) / (long double)((long double)1 - pow(1 - p,v[i].size())) * (query(n) - query(v[i][k]));

		}

		for(int k = 0;k < v[i].size();++k)

		{

			add(v[i][k],(pow(1 - p,k) * p) / (1 - pow(1 - p,v[i].size())));

		}

	}

	printf("%.2Lf\n",ans);

	return 0;

}