P6089 [JSOI2015]非诚勿扰

非诚勿扰

给定 \(N\) 对男女，和 \(M\) 对关系。

每位女生按照关系编号从小到大以 \(P\) 的概率选择某位男生，在未选择之前不断轮回。

定义两对关系 \((a_1,b_1),(a_2,b_2)\) 为不稳定的，当且仅当女生 \(a_1 < a_2\)，但男生 \(b_1 > b_2\)。

求不稳定关系的期望个数。

假设女生 \(a\) 有 \(k\) 个选择，其中第 \(m\) 个男生被选择的概率为：

\(P(a,m)=(1-P)^{m-1}P+(1-P)^k\times (1-P)^{m-1}P+(1-P)^{2k}\times (1-P)^{m-1}P+\cdots\)

因为轮数可能到无限大，我们不妨考虑其封闭形式：

\(P(a,m)=(1-P)^{m-1}P\times(1+(1-P)^k+(1-P)^{2k}+\cdots)\)

设 \(x=(1-P)^{m-1}P,y=(1-P)^k\)，则有：

\(P(a,m)=x\times \frac{1-y^{\infty}}{1-y}\)

因为 \(0.4\leq P<0.6\)，所以 \(y^\infty\) 可以等价于 \(0\)。

故 \(P(a,m)=x\times \frac{1}{1-y}\)，这是可以 \(O(1)\) 简单计算的。

然后如果直接枚举的话，\(O(n^2)\) 还是不行。

但是这是经典的二位数点问题，所以可以直接树状数组维护。

于是就 \(O(n\log n)\) 解决了。

#include
#include
#include
#include
using namespace std;

typedef double DB;
const int N = 500010;
int n, m, deg[N], cnt[N];
DB P, Pow_P[N], c[N];
struct Relat{int u, v; DB p;} R[N];

bool cmp(Relat x, Relat y){
	if(x.u != y.u) return x.u < y.u;
	return x.v < y.v;
}

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

void Modify(int x, DB v){for(; x <= n; x += x & -x) c[x] += v;} 
DB Ask(int x){DB sum = 0.0; for(; x; x -= x & -x) sum += c[x]; return sum;}

int main(){
	n = read(), m = read();
	scanf("%lf", &P);
	for(int i = 1; i <= m; i ++){
		int u = read(), v = read();
		R[i] = (Relat){u, v, 0.0};
		deg[u] ++;
	}
	sort(R + 1, R + m + 1, cmp);
	Pow_P[0] = 1.0;
	for(int i = 1; i <= n; i ++)
		Pow_P[i] = Pow_P[i - 1] * (1.0 - P);
	for(int i = 1; i <= m; i ++){
		int u = R[i].u;
		R[i].p = P * Pow_P[cnt[u]] / (1.0 - Pow_P[deg[u]]);
		cnt[u] ++;
	}
	reverse(R + 1, R + m + 1);
	int now = 1;
	DB ans = 0.0;
	for(int i = n; i >= 1 && now <= m; i --){
		for(int j = now; j <= m && R[j].u == i; j ++)
			ans += Ask(R[j].v - 1) * R[j].p;
		for(int j = now; j <= m && R[j].u == i; j ++)
			Modify(R[j].v, R[j].p), now = j + 1;
	}
	printf("%.2lf\n", ans);
	return 0;
}