这道题要求处理一个灯链上灯泡颜色的调整操作。灯链有 $n$ 个灯泡，每个灯泡有五种颜色之一（从 a 到 e）。需要进行 $m$ 次操作，每次操作指定一个数字 $p$ 和两种颜色 $a$、$b$，表示将灯链上最左边的 $p$ 个颜色为 $a$ 的灯泡改为颜色 $b$。最终输出所有操作后灯链的颜色序列。

算法解析

该问题需要高效处理大规模操作（$n$ 和 $m$ 最多可达 $10^6$），直接模拟每次操作遍历整个灯链会超时。因此，需要采用更高效的数据结构来维护灯链状态。

核心思想：线段树与颜色映射

1. 线段树维护颜色分布：

   • 使用线段树维护每个区间内五种颜色的数量。线段树的每个节点存储一个数组 sum[5]，表示该区间内每种颜色的灯泡数量。
   • 线段树还维护一个 perm 字段，表示颜色映射关系。这是一个整数，其中每3位表示一个颜色的映射目标（因为颜色只有5种，用3位足够）。初始时，perm 设置为恒等映射，即颜色 a 映射到 a，颜色 b 映射到 b，依此类推。

2. 颜色映射操作：

   • 当需要将颜色 $a$ 改为颜色 $b$ 时，生成一个新的映射关系：颜色 $a$ 映射到 $b$，其他颜色映射到自身。这个映射用整数 perm 表示。
   • 应用映射时，通过位运算快速更新节点的颜色统计和当前映射关系。例如，如果当前节点有映射 perm1，新映射为 perm2，则组合映射为 perm2 applied to perm1。

3. 懒标记传播：

   • 当对节点应用映射时，如果节点不是叶子节点，则将映射下推到子节点（懒标记），确保操作高效。
   • 在修改操作中，通过线段树递归查找前 $p$ 个目标颜色灯泡。如果左子树中目标颜色数量足够，则整个左子树应用映射，并继续在右子树处理剩余数量；否则只在左子树处理。

4. 最终输出：

   • 通过深度优先遍历线段树，收集每个叶子节点的颜色（根据最终映射关系），输出整个灯链的颜色序列。

复杂度分析

• 构建线段树：时间复杂度为 $O(n)$。
• 每次修改操作：由于线段树深度为 $O(\log n)$，每次操作最多遍历 $O(\log n)$ 个节点，因此单次操作时间复杂度为 $O(\log n)$。
• 总复杂度：$O(n + m \log n)$，适用于 $n$ 和 $m$ 达到 $10^6$ 的情况。

算法优势

• 利用线段树和懒标记，避免了直接模拟操作的低效问题。
• 颜色映射通过位运算高效处理，利用了颜色种类少的特点。
• 确保每次操作只影响必要的区间，保证了整体效率。