trick大意

我对于这个trick的理解为：支持位运算的高精度
维护一个以 $b$ 为基数的大数 $N$ ，并支持以下功能：

给定（可能是负）整数 $| x |, | y | ⩽ n$ ，将 $x b^{y}$ 加到 $N$ 。
$N ⩾ 0$ 时，给定 $k$ ，打印 $N$ 的第 $k$ 位数字（指以 $b$ 为基底意义下的）。
检查 $N$ 是正值、负值还是等于 $0$ 。

操作 $O (\log n)$ 均摊时间复杂度和 $O (q)$ 内存。并且只需要map进行实现，相比于线段树等数据结构维护非常的好写。

例题及实现： [NOI2017] 整数

题意简述：一个整数 $x$ ，进行 $n$ 次操作，分为两种：

将 $x$ 加上整数 $a \cdot 2^{b}$ ，其中 $a$ 为一个整数， $b$ 为一个非负整数
询问 $x$ 在用二进制表示时，位权为 $2^{k}$ 的位的值（即这一位上的 $1$ 代表 $2^{k}$ ）

保证在任何时候， $x ⩾ 0$ 。

对于所有测试点，满足 $| a | ⩽ 10^{9}$ ；
对于所有测试点，满足 $0 ⩽ b, k ⩽ 30 n$ ；
对于所有测试点，满足 $n ⩽ 1000000$

这里我们的基底为 $2^{30}$ ，感性理解一下：把 $x$ 的二进制表示分为若干段，每一段长是 $30$ 位，这样每次我们只需要改动最多两段，分别对这两段将原数字位运算为相应位后直接加到数中，多于 $2^{30}$ 的进行进位操作。

发现其实很像一个 $2^{30}$ 进位制，这也是以 $b$ 为基底的真正含义

关于均摊时间复杂度

其实我不是很能证明，但是再次感性理解，就是假设一些段内的数为 $[2^{30} - 1, 2^{30} - 1, 2^{30} - 1, 2^{30} - 1. . .]$ 即对应二进制内全为 $1$ 。
显然加一次，他就会往后进很多位花大量时间，虽然这一次花了很多时间，但是呢，需要进位的次数其实是很少的，而不需要进位的时候，直接加又很快，这样下来我们的均摊时间就不是那么慢了。