A4686 | 考拉兹猜想

考拉兹猜想（Collatz conjecture），又称为奇偶归一猜想、$3n+1$ 猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想。

指对于每一个正整数，如果它是奇数，则对它乘 $3$ 再加 $1$；如果它是偶数，则对它除以 $2$，如此循环，最终都能够得到 $1$。

即对于任意正整数 $n$，我们定义

$$ f(n) = \begin{cases} n / 2 &\tt{if\ n \equiv 0 \pmod{2}}\\ 3n + 1 &\tt{if\ n \equiv 1 \pmod{2}} \end{cases} $$

现重复执行该运算，形成一个序列，从任意正整数开始，把每步的结果作为下一步的输入。可记作：

$$ a_i = \begin{cases} n &\tt{i = 0}\\ f(a_{i - 1}) &\tt{i > 0} \end{cases} $$

考拉兹猜想是：所有正整数最终都会到达 $1$，即对于上式，存在 $i$ 使得 $a_i = 1$。

迄今为止，该猜想经过计算验证，所有不超过 $2^{68} \approx 2.95 \times 10^{20}$ 的正整数，经过上述计算都可以得到 $1$。

给定一个长度为 $N$ 的数组 $A_1, A_2, \cdots, A_N$。

你需要执行 $Q$ 个操作，第 $i$ 个操作的类型为 $T_i$：
- $T_i = 1$：给定两个整数 $L_i$ 和 $R_i$，对数组中 $[L_i, R_i]$ 区间内所有大于 $1$ 的元素 $A_i$ 变为 $f(A_i)$。
- $T_i = 2$：给定两个整数 $L_i$ 和 $R_i$，统计数组中区间 $[L_i, R_i]$ 内值为 $1$ 的元素的个数。

$\large{数据范围}$

- $1 \le N,\ Q \le 2 \times 10^5$
- $T_i = 1$ 或 $2$
- $1 \le A_i \le 10^5$
- $1 \le L_i \le R_i \le N$
- 题目保证至少有 $1$ 个操作的类型为 $T_i = 2$。

对于每个测试文件输入格式如下：

$\tt{N\ Q}$

$\tt{A_1\ A_2\ \cdots\ A_N}$

$\tt{T_1\ L_1\ R_1}$

$\tt{T_2\ L_2\ R_2}$

$\tt{\vdots}$

$\tt{T_Q\ L_Q\ R_Q}$

对于所有的 $T_i = 2$ 在单独的一行中输出数组中区间 $[L_i, R_i]$ 内值为 $1$ 的元素的个数。