CF453E 题解

· · 题解

首先考虑简单的情况：假如 a_i 均为 0 ，可以算出这个点最小需要几时才能到最大值 m_i，记为 f_i，显然 f_i = \lceil \dfrac{m_i}{r_i}\rceil，注意特判 r_i=0。

由于操作完 s_i 清空，可以看作推平操作，于是容易想到用珂朵莉树维护修改的时间，那么下一次这个块的增长的时间是一致的。

于是问题变为：求一段区间 s_i 均为 0，过 t 秒后的和。可以发现每个点分两种情况：

由于 t 相同，第二类的点可以把 t 提出来，变成求满足 f_i > t 的点的 t_i 和。

可以预先把每个点放到横坐标代表 i，纵坐标代表 f 的二维平面上，第 i 个点的坐标则为 (i,f_i)，权值为 m_i 或 r_i（如图，图中放一个平面了，比较好看）。

那么每次询问相当于可以分开求这两类点，对于第一类点，可以在维护 m 的二维平面中求 [l,1,t-1,MAX] 矩形的点权和。对于第二类点，就是在维护 r 的二维平面内 [l,t,r,MAX] 矩形的点权和。于是离线下来扫描线，扫描线可以用树状数组比较快。

然后当 a_i\not = 0 时，处理也很简单，只需要在第一次修改时暴力处理，之后便都可以看成 0 了。

code