P5068 我回来了

据说这是一道“很能展现线段树灵活性”的题目。

（老师口头讲太快了我得记一下才能听懂。）

题意建模

所有随从的血量构成一个数列 $H=\{h_i\}_1^p$ （有 $p$ 个随从），在这里我们假设数列是升序排列的（单调不减）。操作 1 就是在 $H$ 里插入新的元素。

操作2 的解释：从一个区间 $[L,R]$ 中等概率地选择一个 $d$ （注意 $L,R,d\in\mathbb{Z}$ ）我们也可以这样看：

D=\{d_i\}=\{L,L+1,...,R-1,R\}.

设 $f(d_i)=k$ 表示：最小的伤害次数 $k\in\mathbb{Z}$ ，使得对所有随从，每次造成 $d_i$ 点伤害，第 $k$ 次伤害时恰好没有随从死亡。所以：

E=\frac{\sum_{d_i\in D}{f(d_i)}}{R-L+1}.

（注意 $D$ 的大小就是 $R-L+1$ ）

说人话就是在（ $d$ 的取值区间） $[L,R]$ 上求 $f(d_i)$ 的平均数。

但是呢，题目让我们输出 $(R-L+1)E$ ，所以我们要求的是：

\text{Ans}=\sum_{d_i\in D}{f(d_i)}=\sum_{j=L}^R{f(j)}.

说人话就是在 $[L,R]$ 上对 $f(d_i)$ 求和。

我们对一个单独的 $d$ 分析， $f(d)$ 是什么意思。
假设 $d=5$ ， $H$ 如下：

H=\{1,2,3,4,5,\space\space 6,7,8,9,10,\space\space11,12,13,14,15,\space\space \dots\}.

公式是有点丑，但是看得出来，前 5 个随从第 1 次就死了，再 5 个随从第 2 次就死了，等等。

这就是说（对于任意 $d$ ）：

H=\{1\dots d,\space\space d+1\dots2d,\space\space 2d+1\dots3d,\space\space\dots\}.

我们发现 $H$ 被分为了若干组，第 $i$ 组随从会在第 $i$ 次伤害中死去。

实际的数据中，不一定每组都会存在，每组不一定个数相同， $H$ 也不一定从 $1$ 开始，但是这里先不纠结这个细节。

还记得 $f(d)$ 的定义么？最小的伤害次数 $k$ ，使得第 $k$ 次伤害时没有随从死亡。那么，如果第 $k$ 次伤害时没有随从死亡，只有一种情况：

又可以细分两种情况：

考虑，对于一个固定的 $H$ ，如果此时的 $d$ 满足情况 2， $f(d)$ 将取得最大值。也就是说：

f(d)\leq \frac{p}{d}.

前提似乎是每个随从的血量互不相同？

不过老师就是这样写的。

所以：

\text{Ans}=\sum_{j=L}^R{f(j)}\leq\sum_{j=L}^R\frac{p}{j}\approx p(\ln R-\ln L).

也就是说伤害次数在 $O(n\log n)$ 级别。

好的，让我们重新捋一下题目吧。现在问题被我们转化为了：

诶，维护区间和？不管那么多了，上线段树吧！

再看看题目：

$1\leq n\leq 10^5$ ， $1\leq L\leq R\leq n$ 。

很好啊，那我们就在 $[1,n]$ 上建立一棵线段树 $tree[\space]$ ， $tree[j]$ 就维护 $f(j)$ 的值。操作 2 我们一个 $\text{getsum}()$ 就可以 $O(\log n)$ 解决。