题意
珂朵莉在玩炉石时重新定义操作“亵渎”为：“等概率随机在 $[L,~R]$ 中选出一个整数作为伤害值 $d$，对所有随从造成 $d$ 点伤害，如果有随从死亡，则再次施放该法术，但伤害值不重新随机；如果没有随从死亡，则停止释放”。
接下来珂朵莉要进行 $m$ 个操作，每个操作为下面两类：
- 在场面上加入一个血量为 $h$ 的随从。
- 给定 $L,~R$，询问亵渎触发次数的期望乘上 $R-L+1$ 后的结果。
$h \le n \le 10^5,~m \le 10^6$
分析
容易发现询问内容“期望乘上 $R-L+1$ 后的结果”即为对于每个 $d \in [L,~R]$ 产生的亵渎触发次数之和。
令 $a[i]$ 表示是否有血量为 $i$ 的随从，则容易发现对于每个 $d$ 其亵渎触发次数为最小的 $k$ 使得满足下列条件：
$$ \sum_{i = d \times k + 1}^{(d + 1) \times k} a[i] = 0 $$
即最小的 $k$ 使得场上不存在血量在 $[d \times k + 1,~ (d + 1) \times k]$ 范围内的随从。
如果我们对于每一个 $d$ 均将 $[1,~n]$ 划分为 $\lceil \frac n d \rceil$ 个长度为 $d$ 的区间，在询问时对于该 $d$ 值亵渎触发次数即为最小的满足区间内 $a[i]$ 都等于零的区间编号。
对于所有合法的 $n$ 个 $d$，这样的区间数量为 $\sum_{i=1}^{n} \frac n i = O(n \log n)$，其数量并不是非常多，因此我们可以考虑将所有询问离线，对每个区间考虑其对答案的贡献。
令 $f[i][j]$ 表示 $d=i$ 时最早于第几次操作后亵渎次数达到 $j+1$，也就是表示最早的对于每个 $t \in [1,~j]$ 均满足 $\sum_{k \in [i \times t + 1,~(i+1) \times t]} a[k] \neq 0$ 的时刻。转移显然为：
$$ f[i][j]=\max(f[i][j-1],~\min_{k \in [i \times j + 1,~(i+1) \times j]}a[k]) $$
转移时第二项最小值使用 ST 表维护，则转移复杂度 $O(n \log n)$。且对于 $d=i$ 时的第 $j$ 块，其会对所有询问时刻大于等于 $f[i][j]$ 的询问产生 $1$ 的贡献。
将所有块的 $f[i][j]$ 值与其对应的 $i$ 值记录下来排序后与询问数组双指针更新答案即可，使用树状数组复杂度 $O(n \log ^2 n + m \log n)$。
Comments | NOTHING