题意理解
食堂网格中，座位位于所有满足 ( x \bmod 3 \neq 0 ) 且 ( y \bmod 3 \neq 0 ) 的区域。
每四个相邻座位构成一张餐桌（即 ( x, y ) 模 3 余 1 或 2）。
顾客从 (0,0) 出发，按曼哈顿距离移动，寻找最近的可用座位。
容忍度 o 决定座位的可用条件：

• o=0：整张餐桌无人
• o=1：相邻座位无人
• o=2：仅要求该座位无人

需要处理两种事件：

1. 新顾客进入，按容忍度选择座位
2. 单个座位状态翻转（有人↔无人）

关键观察

1. 由于座位分布规律，最短距离仅与坐标模 3 的余数有关
2. 可用座位条件可通过维护集合快速查询
3. 最远需要考虑的座位坐标有限（因顾客优先选近的）

算法流程

1. BFS 预计算所有座位的访问顺序

   • 从 (0,0) 开始 BFS 扩展
   • 记录前 ( R ) 个被访问到的座位（( R ) 足够大，覆盖所有可能被选的座位）
   • 将座位按访问顺序编号，存储在 Ord 数组中
   • 同时建立 Id 映射：座位坐标 → 访问序号

2. 状态维护数据结构

   • G 数组标记座位是否被占用（1 为空，0 为占用）
   • P[0], P[1], P[2]：三个 set，分别存储各容忍度下当前可用的座位访问序号
   • Q：存储超出 BFS 范围的座位坐标（大坐标情况）

3. 坐标变换函数 Nxt

   • 将同一餐桌的四个座位映射到标准表示（最小坐标）
   • 通过位操作计算对称变换后的坐标

4. 座位状态翻转函数 flip

   • 处理座位占用状态变化
   • 更新同一餐桌四个座位在各容忍度下的可用状态
   • 在 P[0], P[1], P[2] 中插入/删除对应序号

5. 事件处理

   • 类型 1：从对应 P[o] 中取最小序号（即最近可用座位），输出坐标并调用 flip 占用
   • 类型 2：直接在指定坐标调用 flip，输出状态变化

复杂度分析

• BFS 预计算：( O(R) )
• 每个事件：最多更新 4 个座位状态，set 操作 ( O(\log R) )
• 总复杂度：( O(R + q \log R) )，满足 ( q \leq 5 \times 10^5 ) 要求

算法标签

• 广度优先搜索（BFS）
• 集合维护（set）
• 坐标映射与变换
• 状态压缩与条件判断