【题解】牛客练习赛73

A：

算出最终得分后排序。

然后算出小A需要的最终得分。

然后算出小A需要的高考分。

记得特判0的情况。

[std](https://www.luogu.com.cn/paste/i7t03z3v)

B：
如果一个值相同段用最后一个算贡献，那么连续的1 0答案+1，以及最后一位特判一下。

[std](https://www.luogu.com.cn/paste/rw21jmh7)


C：
从1~n枚举遗憾值为1~n。

设i出现了$c_i$次。

那么这个遗憾值x的生涯回忆录种类就是：$\prod_{i  < x}(2^{c_i}-1) * \prod_{i  > x}(2^{c_i})$。

用前后缀和维护一下就可以O(n)计算所有数的贡献了。

[std](https://www.luogu.com.cn/paste/famdhxwz)

D：

对于每个下标$i$，求出它的一个范围$[x,y]$使得区间$[i,j](x \le j \le y)$中出现最多的数正好出现$k$次。

然后l,r的询问就相当于一个二维数点的问题。

那么树状数组维护一下即可。

O(nlogn)

[std](https://www.luogu.com.cn/paste/b2tqgf7t)

E：

如果已经达到了$a$分，那么相当于就是一个链上随机游走的问题了。

设f[i]表示分差为i的时候的获胜概率，那么$f[i] = (1-p)*f[i-1] + p*f[i+1]$

然后解一下这个方程即可。

对于分不到$a$的，考虑计算出当有人分到达$a$时，分差是$x$的概率。

这个用组合数算一下，具体见代码。

O(nlogn)

[std](https://www.luogu.com.cn/paste/p5jrmelx)

F：

值域分块。

首先确定每个询问的答案在哪个块的范围内，几次前缀和维护一下每个询问里在每个块的范围内出现了多少个数。

然后对于块内的答案，相当于$n \sqrt n$次询问被多少个[L,R]内的区间$[x_i,y_i]$包含。这个拆成$[1,L-1]$的和$[1,R]$的然后减一下。

按照右端点排序，然后就转换成$O(n)$次区间加,$O(n \sqrt n)$次单点询问，这个分块维护即可达到总复杂度$O(n \sqrt n)$。

[std](https://www.luogu.com.cn/paste/qdkk2ui6)