Solution. LG3822 [NOI2017] 整数 / Trygub Numbers
Description
维护一个二进制数 $x$，支持两种操作：
- $x\gets x + a \cdot 2 ^ b$
- 询问 $x$ 第 $k$ 位的值
共 $n$ 次操作。
$1\le n\le 10^6,|a|\le10^9,0\le b,k\le30n$
THUSC 2023 游记
看 THUSC 和 PKUSC 的公告，我本来觉得初审要求挺严格，但是今年居然两边都过了，不过湖北几个初中生好像基本上也是两边都过或者至少过了 PKUSC，说明对初中生还是很宽松的。
Solution. CF441E Valera and Number
$+1$ 操作的贡献不好计算，但是由于操作数很少，我们完全可以记录下最低 $\log k$ 位的状态，这样总状态数是 $O(k^3)$ 的，转移 $O(1)$，故总复杂度 $O(k^3)$。