CF2074F.Counting Necessary Nodes

四叉树是一种树形数据结构，其中每个节点最多有四个子节点，每个节点对应一个正方形区域。

形式化地说，对于所有非负整数 $k, a, b \ge 0$ 的元组，存在且仅存在一个节点对应以下区域 $^{\text{∗}}$：

$$[a \cdot 2^k, (a+1) \cdot 2^k] \times [b \cdot 2^k, (b+1) \cdot 2^k]$$

所有区域大小超过 $1 \times 1$ 的节点都包含四个子节点，这些子节点对应将原区域四等分后的四个子区域；而区域为 $1 \times 1$ 的节点对应树的叶节点。

图中展示了部分节点对应的区域。颜色较深的区域更接近叶节点。

Frontman 厌恶一个普遍的误解——当区域内包含 $n$ 个叶节点时，四叉树可以在 $\mathcal{O}(\log n)$ 时间内完成范围查询。事实上，有时需要查询远多于 $\mathcal{O}(\log n)$ 个区域，极端情况下时间复杂度甚至为 $\mathcal{O}(n)$。因此，Frontman 设计了此题来教育你关于该数据结构的最坏情况。

粉色士兵们给定了一个有限区域 $[l_1, r_1] \times [l_2, r_2]$，其中 $l_i$ 和 $r_i$（$l_i < r_i$）为非负整数。请找出最少需要选择多少个节点，使得这些节点对应区域的并集恰好等于给定区域。这里，两个点集被认为是不同的，当且仅当存在一个点属于其中一个集合但不属于另一个。

$^{\text{∗}}$ 区域是具有实数坐标的点集。点 $(x, y)$ 属于区域 $[p, q] \times [r, s]$ 当且仅当 $p \le x \le q$ 且 $r \le y \le s$。此处 $\times$ 形式上指集合的笛卡尔积。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的唯一一行包含四个整数 $l_1$、$r_1$、$l_2$、$r_2$ —— 各坐标轴的区域边界（$0 \le l_i < r_i \le 10^6$）。

对于每个测试用例，在单独一行中输出满足条件所需的最少节点数量。

第一个测试用例中，给定区域为 $[0, 1] \times [1, 2]$。存在一个节点对应该区域，选择该节点即可，答案为 $1$。

第二个测试用例中，给定区域为 $[0, 2] \times [0, 2]$。存在一个节点对应该区域，选择该节点即可，答案为 $1$。

第三个测试用例中，给定区域为 $[1, 3] \times [1, 3]$。不存在对应该区域的节点。但可以通过选择以下 $4$ 个叶节点构造出相同区域：

• 对应 $[1, 2] \times [1, 2]$ 的叶节点；
• 对应 $[1, 2] \times [2, 3]$ 的叶节点；
• 对应 $[2, 3] \times [1, 2]$ 的叶节点；
• 对应 $[2, 3] \times [2, 3]$ 的叶节点。

可以证明无法用少于 $4$ 个节点构造出该区域，因此答案为 $4$。

第四个测试用例中，给定区域为 $[0, 2] \times [1, 5]$。可以通过选择以下 $5$ 个节点构造出相同区域：

• 对应 $[0, 1] \times [1, 2]$ 的叶节点；
• 对应 $[1, 2] \times [1, 2]$ 的叶节点；
• 对应 $[0, 2] \times [2, 4]$ 的非叶节点；
• 对应 $[0, 1] \times [4, 5]$ 的叶节点；
• 对应 $[1, 2] \times [4, 5]$ 的叶节点。

可以证明无法用少于 $5$ 个节点构造出该区域，因此答案为 $5$。

翻译由 DeepSeek R1 完成