引言

今年命题会的时候，我们惊奇地发现今年的模拟题还没有着落。

于是我翻出了这个压箱底的 idea，当作一个中模拟。

idea 恰如其分来自在你清食堂的吃饭经历，获得了大家的一致认同。

时限只开 3s 是因为有 100 个点，开太久会更严重地卡评测的。std 跑了 1.6s。出题人试图开 5s 被系统部和赛务部的同学们拦下了

比赛情况

本题的完整版本预期难度是 medium，不过我个人认为是 easy+（？）。

丝路市西套村代表队获得了本题首杀！

本题大约有一半的队伍通过了本题。

同时，不少夺冠热门队伍在本题上获得了大量罚时。

题意简述

食堂餐桌座位分布在第一象限网格每个 $3 \times 3$ 完整格子右上角的 $2 \times 2$ 格子，剩下的部分为走廊。

每次可以从一个走廊格子走到四连通相邻格子。

每次一名顾客从最左下角的格子出发，试图找到最优的一个满足自己容忍条件的空座位。容忍条件形如桌子上坐了几人以及自己因此应该去哪里（请参考原题面）。

此外还会有部分座位突然出现或消失顾客，也即状态翻转。

输出每次顾客坐到了哪里，以及突然变化的顾客是来是去。

操作次数 $q$ 不超过 $5 \times 10^5$。第二类操作值域不超过 $10^4$ 且总是修改在餐桌处。3s/1GB。

思路

本题总体思路比较简单，这里直接给出完整版正解做法。

注意到第一类操作可能遇上的下标范围是 $O(\sqrt{q})$ 级别的，我们不妨考虑做预处理。

观察到其优先顺序是固定的，我们可以预先排序得到各个餐桌格子的优先顺序。这个排序可以通过数学方法或者 bfs 做到线性。

考虑第一类操作，我们可以用 set 或可删堆（对顶堆）存一下每个满足对应条件的位置。

第二类操作对于下标超界的部分也可以单独拿一个 set 存；没超界的部分可以和前面的部分使用同一套方法处理。

不用太多卡常，验题人开了八九个 set 都过了。std 不到 2kb。

本题非常善良，值域只开 $10^4$ 是为了方便压位（记得用 $10001$ 压）。没有特意卡 umap/bitset 之类的东西，应该是可以轻松过的。

总结

• 在这样一场毒瘤的比赛中，
• 这道题目无疑是出题人无私的馈赠，
• 经典的模型、较低的难度和不大的代码量，能帮助你把分数收入囊中
• 出题人相信，这个美妙的题目，可以给拼搏于 XCPC 的追梦之路上的你，提供一个有利的援助。