LG5068 [Ynoi2015] 我回来了

发布于 2021-07-22  1.63k 次阅读


题目链接

题意

珂朵莉在玩炉石时重新定义操作“亵渎”为:“等概率随机在 $[L,~R]$ 中选出一个整数作为伤害值 $d$,对所有随从造成 $d$ 点伤害,如果有随从死亡,则再次施放该法术,但伤害值不重新随机;如果没有随从死亡,则停止释放”。

接下来珂朵莉要进行 $m$ 个操作,每个操作为下面两类:

  1. 在场面上加入一个血量为 $h$ 的随从。
  2. 给定 $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)$。

代码

View on GitHub


我缓慢吐出一串啊吧啊吧并不再想说话