Educational Codeforces Round 119

C

BA-String
题目大意
给你一个串，仅由字符 a 和 * 构成
现在可以将 * 替换成 $[0, k]$ 个 b，求字典序第 $x$ 小的串

不难想到应该从后往前扫描，贪心思路是，能换后面的 * 就尽可能换后面的
先对串进行预处理，计算出被 a 分隔开的一段一段的 * 有多少个？ $\text{cnt}(i)$ 表示第 $i$ 段有多少个 *

对于每一段而言，它能够替换的 $b$ 最多有 $num(i) = 1 + k \cdot cnt(i)$ 个
从后往前扫描 $cnt$ 数组，如果 $x < num(i)$ ，那么往前所有的 * 都不用替换，直接删掉
如果是 a 就接到答案中，否则的话，还需要在前面替换 $x'$ 个 $b$

那么此时 $x$ 的排名是多少？ $x = x' \cdot num(i) + r(i)$ ，也就是说，在第 $i$ 段需要替换 $r(i)$ 个 $b$ 就可以了
于是 $x \leftarrow x / num(i), \ r(i) = x \bmod num(i)$

最后得到 $r(i)$ 就是第 $i$ 段应该替换为多少个 $b$

动态开点线段树

Mountains
题目大意
给定过山车，初始时在起点高度为 $0$ 处，给一些操作， $I\ a \ b\ D$ 表示将 $[a, b]$ 区间高度设为 $D$
过山车给个值 $h$ ，只要没到终点或者高度 $\leqslant h$ ，过山车会一直往前走，求过山车最后能走多远

对应每个询问，实际上是给定数组 $A[i]$ ，求满足前缀和 $S(i) \leqslant h$ 的最右边的位置 $i$
考虑用线段树维护最大非负前缀和 $maxp$ ，对应走过这一段区间需要的代价
$h$ 表示当前过山车剩余的能量，如果 $h \leqslant maxp$ ，说明会停留在这个区间中， $h > maxp$ 才能通过这个区间

不难想到，线段树首先要维护一个 $sum$ 表示区间元素的和
那么最大非负前缀和如何求？对于一维序列的情况，有如下递推
如果 $A_i \geqslant 0$ ，那么 $S(i) = S(i-1) + A(i)$ ，如果 $A_i < 0$ ，那么 $S(i) = S(i-1)$ ，等价于令 $A(i) = 0$
对应到线段树中，对于区间 $[l, r]$ ，如果这一段的值 $< 0$ ，就将这一段区间值取 $0$
于是我们线段树维护 $maxp$ ，表示该区间 $[l, r]$ 对 $1 \to r$ 的最大非负前缀和的贡献
假设当前结点为 $p$ ，子节点分别为 $pl, pr$ ，那么 $\textbf{pull}$ 的时候令
$p.maxp = \max \{pl.maxp, pl.sum + pr.maxp, 0\}$
另外，进入区间时能量为 $h$ ，离开区间时能量应该转移到 $h - p.sum$
递归左子树时候用 $h$ ，递归右子树的时候对应 $h - pl.sum$

最后是如何确定过山车停在区间的哪个位置？

如果 $h \geqslant p.maxp$ ，假设 $p$ 对应的区间为 $[l, r]$ ，过山车能够停在 $r$ 处
如果 $h < p.maxp$ ，那么过山车会在 $p$ 中间的某一个位置停下来，这时候考虑区间的斜率
若区间的斜率都相等，均为 $v$ ，那么过山车的位置在 $l + (h / p.v) - 1$
否则，递归子区间，如果 $h < pl.maxp$ ，那么过山车停在左子区间中，否则 $h \leftarrow h - pl.sum$ ，递归右子树

综上所述，我们只需要再维护一个斜率，这个问题就可以解决了

需要优化空间，用动态开点线段树

仅创建从 $\text{root}$ 到目标区间 $[L, R]$ 路径上的结点，其他结点不需要创建
编程实现的时候，把 $\textbf{new}$ 新结点的语句放在 $\textbf{push}$ 函数中，当需要 $\text{push}$ 的时候
$pl \leftarrow \textbf{new}, \ pr \leftarrow \textbf{new}$ ，然后下传标记并更新 $pl, pr$
当一个区间的斜率都相同时，不需要子节点，删除左右子节点并回收内存