Trygub Number

参考资料

做 「NOI2017」整数 的时候了解到有这个东西，支持对于 \(B\) 进制数 \(X\)：

• 加上 \(x\cdot B^y\)，复杂度为 \(\mathcal{O}(\log V+\log n)\)。
• 查询第 \(k\) 位的值，复杂度为 \(\mathcal{O}(\log V+\log n)\)。

复杂度是瞎写的，反正就是一个 \(\log\)。

具体思路是维护一个序列 \(a\)，其中 \(a_i\in(-B,B)\)，\(X=\sum_{i\geq 0} a_iB^i\)，每次加的时候暴力进位。为了方便查询，我们用 map 维护所有非 \(0\) 位置，然后在查询的时候 lower_bound 一下看有没有进位即可。

先说明进位次数是正确的。假设 \(X\) 为当前位的值，它贡献到下一位的值为 \(X/B\)。分两部分考虑进位：

• \(X\geq 2B\)，显然它会在 \(\log V\) 轮之后变成下一种情况。
• \(X<2B\)，此时它对下一位的贡献为 \(1\)。定义势能函数为“临界位置”的值，即 \(|a_i|=B-1\) 的位置个数。在这种情况下，一次进位至少消耗一个临界位置。而一次操作至多增加一个临界位置，所以均摊正确。

由于查询需要利用 map 维护值，所以此时的复杂度是 \(\mathcal{O}(\log V\log n)\)，还能再优化吗？

注意到我们修改的 map 的迭代器是连续的，你可以用 loj 上的一个帖子类似的技巧做到均摊常数访问一段连续的迭代器。所以复杂度降到了一个 \(\log\)。

\(\mathcal{O}(\log V\log n)\) 代码

\(\mathcal{O}(\log V+\log n)\) 代码

当然可以用压位做到更快，但相信没有无良出题人卡这个算法。