BZOJ4942 [NOI2017] 整数
你要维护一个二进制数 $x$ ,有 $n$ 个操作:
1 a b ,表示 $x \mathrel{+}= a \times 2^b$ ;
2 k ,表示询问 $x$ 第 $k$ 个二进制位的值.
初始时 $x = 0$ .
$n \leqslant 10^6, |a| \leqslant 10^9, b, k \leqslant 3 \times 10^7$
先考虑只有 $a > 0$ 的时候怎么做.
考虑暴力:把 $a$ 的每一位拆开加;每次要在第 $i$ 位上加的时候不停往前进位直到进不上去为止.
分析一下复杂度:
每次加的时候会把某一些二进制位从 1 变成 0 ,但是