题目描述

小蓝构造了一棵特殊的二叉树，节点有红黑两种颜色。构造规则如下：
1. 根结点 (第 1 行第 1 个) 是红色。
2. 红色结点的左子结点是红色，右子结点是黑色。
3. 黑色结点的左子结点是黑色，右子结点是红色。

给定 $m$ 个查询，每个查询给出结点的层数 $n_i$ (从 1 开始) 和该层从左到右的序号 $k_i$ (从 1 开始)，要求判断该结点的颜色是红色 (RED) 还是黑色 (BLACK)。

样例

输入:
2
1 1
2 2

输出:
RED
BLACK

说明:
查询 1: 第 1 行第 1 个结点是根结点，按规则 1 是红色。
查询 2: 第 2 行第 2 个结点是根结点的右子结点。根是红色，按规则 2，右子结点是黑色。

算法1 (位运算 - Popcount 奇偶性)

$O(m)$ 或 $O(m \log k)$

思路分析

1. 观察树的结构和颜色规律:
   我们先手动构造前几层，标记颜色 (R=Red, B=Black)：

   • Level 1: R (k=1)
   • Level 2: R B (k=1, k=2) (根 R -> 左 R, 右 B)
   • Level 3: R B B R (k=1,2,3,4) (父 R -> R B, 父 B -> B R)
   • Level 4: R B B R B R R B (k=1..8) (父 R->RB, 父 B->BR, 父 B->BR, 父 R->RB)

2. 颜色变化的本质:
   从根节点 (RED) 出发到达目标节点 $(n, k)$，路径上每一步移动都会根据规则 2 和规则 3 确定子节点的颜色。我们观察颜色何时会翻转 (相对于根节点的红色)：

   • 从 RED 父节点到左子节点 (RED): 颜色不变 (R->R)
   • 从 RED 父节点到右子节点 (BLACK): 颜色翻转 (R->B)
   • 从 BLACK 父节点到左子节点 (BLACK): 颜色不变 (B->B)
   • 从 BLACK 父节点到右子节点 (RED): 颜色翻转 (B->R)
     关键发现: 无论父节点是什么颜色，向右移动总会导致颜色相对于父节点发生改变（R变B，B变R），而向左移动总会保持与父节点相同的颜色类型。
     因此，一个节点的颜色取决于从根节点到该节点的路径中，向右移动的次数。如果向右移动了偶数次，颜色与根节点相同（红色）；如果向右移动了奇数次，颜色与根节点相反（黑色）。

3. 路径与节点位置 k 的关系:
   考虑一个节点在第 $n$ 行，位置为 $k$ (1-based)。

   • 它的父节点在第 $n-1$ 行，位置为 $\lceil k/2 \rceil = (k+1)/2$ （整数除法）。
   • 如果 $k$ 是奇数，那么该节点是其父节点的左子节点。
   • 如果 $k$ 是偶数，那么该节点是其父节点的右子节点。
     这意味着，从 $(n, k)$ 向上回溯到根 $(1, 1)$，每当 $k$ 是偶数时，就表示在从父到子的路径上发生了一次向右的移动（颜色翻转）。

4. 连接 $k$ 与颜色翻转次数:
   我们从 $(n, k)$ 向上回溯，记录 $k$ 是偶数的次数，这个次数就是总的颜色翻转次数。
   回溯过程：当前节点 $(cn, ck)$，父节点 $(cn-1, (ck+1)/2)$。
   当 $ck$ 为偶数时，翻转次数加 1。

5. 二进制表示的洞察:
   考虑节点位置的 0-based 索引 $k’ = k-1$。

   • $k$ 是偶数 $\iff k-1$ 是奇数 $\iff k’$ 的二进制表示最低位是 1。
   • $k$ 是奇数 $\iff k-1$ 是偶数 $\iff k’$ 的二进制表示最低位是 0。
     父节点的 0-based 索引是 $\lfloor (k-1)/2 \rfloor = (k-1) \gg 1 = k’ \gg 1$。
     向上回溯一步并将 $k$ 更新为其父节点的索引，相当于将 $k’$ 右移一位。
     在回溯过程中，检查 $k$ 是否为偶数，等价于检查当前 $k’$ 的最低位是否为 1。
     因此，从 $(n, k)$ 向上回溯到根，总的颜色翻转次数等于 $k’ = k-1$ 的二进制表示中 1 的个数 (population count 或 popcount)。

6. 最终结论:
   节点 $(n, k)$ 的颜色取决于 $k-1$ 的二进制表示中 1 的个数的奇偶性。

   • 如果 popcount(k-1) 是偶数，颜色为红色 (RED)。
   • 如果 popcount(k-1) 是奇数，颜色为黑色 (BLACK)。
     注意：这个结论与层数 $n$ 无关！

7. 代码实现:

   • GCC/Clang 提供了内置函数 __builtin_popcount(x) 计算 x 的二进制中 1 的个数，以及 __builtin_parity(x) 直接计算 popcount 的奇偶性 (返回 1 表示奇数个 1，返回 0 表示偶数个 1)。
   • 代码 __builtin_parity(k-1) 直接计算了 $k-1$ 的 popcount 的奇偶性。
   • 如果 __builtin_parity(k-1) 返回 1 (奇数)，则输出 “BLACK”。
   • 如果 __builtin_parity(k-1) 返回 0 (偶数)，则输出 “RED”。

时间复杂度

对于每个查询，计算 k-1 的 popcount 奇偶性。如果使用 __builtin_parity，这通常是一个非常快的硬件指令，可以认为是 $O(1)$。如果不使用内置函数，手动计算奇偶性的时间复杂度是 $O(\log k)$。
由于有 $m$ 个查询，总时间复杂度为 $O(m)$ 或 $O(m \log (\max k_i))$。考虑到 $k_i \le 2^{n_i-1}$ 且 $n_i \le 30$，$\log k_i$ 最多约为 30，所以复杂度非常低。

C++ 代码 (算法 1)

#include <iostream> // 引入标准输入输出库
using namespace std; // 使用标准命名空间

int main() {
    int m; // 查询次数
    cin >> m; 
    for (int i = 0; i < m; i++) { // 处理 m 次查询
        int n, k; // 输入层数 n 和位置 k (注意：代码中实际只读入了 k 两次，n 被覆盖了)
                 // 幸运的是，根据推导，n 的值并不影响结果！
        cin >> k >> k; // 读入 n 和 k，但 n 的值被第二次读入的 k 覆盖了
                       // 等价于只读入了 k

        // __builtin_parity(k-1) 计算 k-1 的二进制表示中 1 的个数的奇偶性
        // 返回 1 表示奇数个 1 (对应 BLACK)
        // 返回 0 表示偶数个 1 (对应 RED)
        cout << (__builtin_parity(k - 1) ? "BLACK\n" : "RED\n"); 
        // 使用三元运算符根据奇偶性输出结果
    }
    return 0; // 程序正常结束
}

算法2 (路径回溯模拟)

$O(m \times n)$

思路分析

1. 基本原理: 如算法 1 分析所述，节点的颜色取决于从根到该节点的路径上发生颜色翻转的次数（即向右走的次数）。如果翻转次数为偶数，颜色为 RED；如果为奇数，颜色为 BLACK。

2. 回溯过程: 我们可以直接模拟从目标节点 $(n, k)$ 向上走到根节点 $(1, 1)$ 的过程，并统计这个过程中有多少步是从右子节点走向父节点的（即当前 $k$ 是偶数）。

3. 模拟步骤:

   • 定义函数 get_color(n, k) 来计算节点 $(n, k)$ 的颜色。
   • 初始化翻转次数 flips = 0。
   • 使用变量 cn 和 ck 分别表示当前节点所在的层数和该层的位置，初始值为输入的 n 和 k。
   • 循环进行，只要当前层数 cn > 1（还没到达根节点）：
     a. 检查当前位置 ck 是否为偶数。如果是偶数，说明这一步是从右子节点回溯到父节点，发生了一次颜色翻转，flips++。
     b. 计算父节点的位置：ck = (ck + 1) / 2。
     c. 移动到上一层：cn--。
   • 循环结束后，flips 存储了总的颜色翻转次数。
   • 根据 flips 的奇偶性返回最终颜色：flips % 2 ? BLACK : RED （奇数次翻转为 BLACK，偶数次翻转为 RED）。

4. 主程序:

   • 读取查询次数 $m$。
   • 循环 $m$ 次：
     a. 读取 $n_i, k_i$。
     b. 调用 get_color(n_i, k_i) 得到颜色。
     c. 根据返回的颜色（RED 或 BLACK）输出相应的字符串。

时间复杂度

对于每个查询 $(n, k)$，get_color 函数中的 while 循环执行 $n-1$ 次。循环内部的操作都是常数时间。因此，处理一个查询的时间复杂度是 $O(n)$。
总共有 $m$ 个查询，所以总时间复杂度为 $O(m \times \max n_i)$。考虑到 $n_i \le 30$，这完全在时间限制内。

C++ 代码 (算法 2)

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long (本题未使用)

const int RED = 0;   // 定义常量表示红色
const int BLACK = 1; // 定义常量表示黑色

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    // 定义 lambda 函数 get_color，计算节点 (n, k) 的颜色
    auto get_color = [](int n, int k) {
        int flips = 0; // 初始化颜色翻转次数为 0
        int cn = n;    // 当前层数
        int ck = k;    // 当前层的位置 (1-based)

        // 从 (n, k) 向上回溯到根 (层数 > 1)
        while (cn > 1) {
            // 如果当前位置 ck 是偶数，说明是从右子节点来的，发生一次翻转
            if (ck % 2 == 0) {
                flips++;
            }
            // 计算父节点的位置 (向上移动一层)
            ck = (ck + 1) / 2; 
            // 移动到上一层
            cn--;
        }
        // 根据总翻转次数的奇偶性返回颜色
        // 偶数次翻转 -> RED (0)
        // 奇数次翻转 -> BLACK (1)
        return flips % 2 ? BLACK : RED; 
    };

    int m; // 查询次数
    cin >> m;
    // 处理 m 次查询
    while (m--) {
        int n, k; // 输入层数 n 和位置 k
        cin >> n >> k;
        // 调用 get_color 计算颜色并输出结果
        cout << (get_color(n, k) == RED ? "RED\n" : "BLACK\n");
    }

    return 0; // 程序正常结束
}