🧩 问题核心分析

题目要求我们处理两种任务：

1. 模拟给定操作：按顺序执行玩家的操作，计算他能消除多少棋子。
2. 寻找最优方案：找出一套操作序列，使得消除的棋子数量尽可能多。

游戏规则核心：

• 操作必须从空格子开始。
• 选择两个方向，每个方向上的第一个棋子必须颜色相同。
• 满足条件则消除这对棋子，空出位置。

关键点：

• 棋盘很大，最多 $10^5 \times 10^5$ 的网格，但棋子只有 $2n$ 个（$n \leq 10^5$），所以棋盘是稀疏的。
• 需要快速查找从某个空格子出发，在指定方向上遇到的第一个棋子是什么。

💡 核心思路：使用有序集合维护棋子位置

由于棋盘稀疏，我们可以不为每个格子分配存储，而是用高效的数据结构记录棋子的位置。

🔹 数据结构设计

为每一行和每一列建立有序集合（如 C++ 的 std::set）：

• row_set[i]：存储第 i 行所有棋子的列坐标（也可以同时记录颜色）。
• col_set[j]：存储第 j 列所有棋子的行坐标。

为什么这样设计？

• 有序集合支持快速查找前驱和后继，这正是我们“沿着方向找第一个棋子”所需要的。
• 插入、删除操作都是 $O(\log n)$ 的，效率很高。

🔹 方向查找的实现

以从 (x, y) 出发为例：

• 向右查找：在 row_set[x] 中找第一个大于 y 的元素。
• 向左查找：在 row_set[x] 中找第一个小于 y 的元素。
• 向上查找：在 col_set[y] 中找第一个小于 x 的元素。
• 向下查找：在 col_set[y] 中找第一个大于 x 的元素。

这可以通过 lower_bound、upper_bound 或直接遍历有序集合来实现。

🧮 算法实现步骤

1. 模拟给定操作（任务一）

// 伪代码框架
初始化 row_set 和 col_set，插入所有棋子的位置
记录已消除的棋子对数 ans = 0

for 每个操作 (x, y, dir1, dir2):
    if (x, y) 不是空格: // 检查该位置是否在任意集合中存在
        continue
        
    p1 = 在 dir1 方向上从 (x,y) 找到的第一个棋子
    p2 = 在 dir2 方向上从 (x,y) 找到的第一个棋子
    
    if p1 和 p2 都存在且颜色相同:
        从 row_set 和 col_set 中删除 p1 和 p2 的位置
        ans += 2 // 因为消除了两个棋子
输出 ans

2. 寻找最优方案（任务二）

这是一个更具挑战性的问题，目标是消除尽可能多的棋子。这里提供一种贪心策略作为参考：

1. 遍历所有空格子：对于每个空格子 (x, y)，检查所有可能的方向组合（如 (上, 左)，(上, 右) 等）。
2. 评估消除机会：对于每个方向组合，找出两个方向上第一个棋子的颜色。如果颜色相同，这是一个潜在的消除操作。
3. 选择策略：有多种策略可以选择下一步操作：
   • 立即消除：一旦找到一对可消除的棋子，就立即消除。这是最直接的策略。
   • 全局最优：评估所有可能的消除操作，选择一种能为后续操作创造更多空格子或避免阻塞关键路径的操作。这通常更优，但计算成本更高。
4. 迭代消除：重复上述过程，直到没有更多的消除操作为止。

注意：寻找全局最优解可能非常困难，在时间限制内得到一个近似最优解（例如使用上述贪心策略）通常是可行的。

⚠️ 注意事项

1. 性能优化：由于 $n$ 最大为 $10^5$，必须确保每次查询都是 $O(\log n)$ 或更优。
2. 重复消除：注意，一对棋子被消除后，它们所在的位置变为空格，可能开启新的消除机会。
3. 操作顺序：在任务二中，不同的操作顺序可能导致不同的消除总数，这也是问题的难点所在。
4. 输出格式：注意输出方案时，需要输出操作序列，包括格子坐标和两个方向。

💎 总结

这道题的核心在于：

1. 数据结构选择：使用有序集合高效管理稀疏棋盘。
2. 模拟效率：快速响应方向查询和棋子消除。
3. 贪心策略：在任务二中，一个简单的贪心策略（如找到一对消一对）通常就能得到不错的结果，但更复杂的策略可能得到更优解。