题解：AT_abc434_g [ABC434G] Keyboard

one_last_kiss · 2025-12-05 19:33:32 · 题解

区间修改查询操作很容易让人想到线段树。

那么一个节点我们该维护哪一些值呢？

::::info[为什么是前缀] 处在数字后面的 B 在子节点合并时一定把前面的数字消掉了，所以不可能出现。 ::::

有了这些数据，我们便可以进行合并。但瓶颈在于 val 存的是取模后的值，而我们需要抵消的是实际数值的后缀。

我们运用类似楼房重建递归合并的方法，定义 ask(p,d) 为 p 的子树内，实际数值的后 d 位是多少。

• 若 d 小于等于右子树的 len，则递归右子树。

• 否则，右子树全被删完了，递归左子树。

这样单次合并是 O(\log n) 的，总时间复杂度为 O(q \log^2 n)。