P3613 寄包柜：哈希表与稀疏数据，比二维数组更优雅的解法

P3613【深基15.例2】寄包柜，算是我刷题过程中印象非常深的一道题。刚拿到题目时，我的第一反应是：这不就是一个二维数组模拟吗？存包、查询，两个操作而已。可等我认真读完题面，再结合它被放在《深入浅出程序设计竞赛（基础篇）》第15章“哈希表”部分的身份，才反应过来，这道题真正的目的不是让你写二维数组，而是让你思考如何用哈希表处理稀疏数据。这篇文章我就围绕它展开，讲讲数据范围怎么逼退朴素方案、三种能AC的写法怎么选、代码每一步在做什么，以及我自己实测踩过的坑。适合正在刷深基、刚开始接触哈希表、或者想搞明白“为什么有些题不能直接开数组”的读者。

1. 看题先算账：数据范围早就决定了二维数组必炸

1.1 题目确实是在模拟存包，但不止于模拟

这道题的题面大致是这样：超市里有 n 个存包柜，每个柜子的格子数可能并不一样。接着给你 q 次操作。第一种操作是1 i j x，表示往第 i 个柜子的第 j 个格子放物品 x；第二种操作是2 i j，表示查询第 i 个柜子第 j 个格子里现在存的物品，如果这个格子从来没被放过东西，就输出 -1。

单看逻辑，确实就是一个“存”一个“取”，没有任何算法含量。甚至你都能预感到它的标程可能很短。但问题是，“第 i 个柜子的第 j 个格子”这个说法，天然就是一个二维坐标。题目所有操作都落在坐标(i, j)上，于是你脑子里很自然地就会蹦出int a[i][j]这样一个二维数组。

如果你只在样例里跑这题，二维数组完全够用。样例小嘛，怎么开都行。但只要把数据规模拉上去，这种朴素解法就会先内存爆炸，再时间超限。所以真正决定这道题解法方向的不是操作逻辑，而是题目最下面那几行不起眼的数据约束。

1.2 内存账：n 乘最大格子数的乘积能吓死人

竞赛题里，n 和数据范围经常是10^5这个量级。假如最坏情况下，柜子数 n 是 10^5，每个柜子的格子数也能到 10^5，那么整个空间里最多需要表示的格子数量就是：

10^5 * 10^5 = 10^10

这还只是格子个数。一个int占 4 字节，那这整张二维表占用的内存就是：

10^10 * 4 = 40GB

你可以感受一下这个量级：普通评测机的内存限制通常是 128MB 或 256MB，40GB 是它的一百多倍。哪怕你很有技巧地使用vector<vector<int>>动态开，一旦有柜子的格子数真的接近上限，照样会爆。这不是写法问题，是数据规模和算法选型根本不匹配。

这里补充一个实测时的直觉，数据范围和内存消耗的关系大致是这样：

所以当你看到这种“两个维度相乘规模巨大”的题，第一件要做的事就是先算账。算完这笔账，二维数组方案就可以直接划掉了。

1.3 操作数 q 带来转机：稀疏数据的关键信号

既然二维空间那么大，为什么题目还能做？因为真正会被我们访问到的格子数量，根本不取决于 n 和格子数的乘积，而是取决于操作次数 q。

每次操作只涉及一个具体的格子(i, j)。q 一般来说也在10^5这个量级。哪怕 q 次操作全部落在不同的格子上，出现过不同坐标的数量最多也就是 q 个。也就是说，在可能高达 10^10 的空间里，真正有数据的格子最多只有 10^5 个。其余格子从头到尾都没被碰过。

这就是典型的稀疏数据场景：潜在空间很大，实际有效值很少。对这种问题，正确做法从来都不是“把整个空间铺开”，而是“按需记录”。哪个格子被操作过，就给哪个格子建立一条记录；没被操作过的格子，不需要占用任何内存。这个思路转过弯来，整道题的解法就很清晰了：我们需要一个字典结构，把坐标作为键，把物品值作为值。

2. 核心原理：哈希表怎么就成了寄包柜的正确答案

2.1 从“提前铺满”到“按需记账”

我用一个生活化的类比来解释为什么要用哈希表。二维数组相当于小区物业提前给每一户人家都装上了一个信箱，哪怕这户根本没人住，信箱也结结实实地占了地方。哈希表则更像寄存处的账本，只有真正有人来存东西时，才在账本上登记一个柜号；没被用过的柜子，账本上空空如也，不占任何资源。

在 C++ 里，这种“按键查找、按键更新”的字典结构，最常见的就是map和unordered_map。map底层是红黑树，按键排序，操作复杂度是 O(log k)，这里的 k 是实际记录数。unordered_map底层是哈希表，平均复杂度 O(1)。两种容器都要求键唯一，这正好满足“一个格子同时只能存一个值”的语义。如果你对同一个(i, j)执行两次放入操作，第二次会直接覆盖第一次的值。

2.2 键值对设计和两种操作如何映射到哈希表

把题目翻译成哈希表的操作，其实是顺理成章的：

• 键是坐标(i, j)。
• 值是格子里存放的物品 x。
• 操作1 i j x等价于box[make_pair(i, j)] = x。
• 操作2 i j等价于在box中查找make_pair(i, j)，找到就输出对应值，找不到说明从没放过东西，输出 -1。

这里要注意，查询时应该用find而不是直接用中括号访问。中括号在键不存在时会默认插入一个值，这会给容器塞入很多并不存在的空记录，后面我会单独讲。

至于复杂度，由于 k 最大不会超过 q，q 又是10^5量级，所以用map的 O(log k) 完全能过，换成unordered_map的平均 O(1) 则更稳。两种方案在这道题里都不会是瓶颈，真正的瓶颈是在“键的设计”上。

2.3 这道题真正想考察的两件事

第一，识别稀疏场景。你要能从“数据范围巨大、操作次数有限”这两个信息里看出，这个问题的有效数据很少，不能直接铺二维数组。第二，设计一个可哈希的键。二维坐标(i, j)怎么变成一个能被容器使用的键？是直接用pair<int,int>？还是自定义哈希？还是压成一个long long？这三种做法分别适合什么场景？这些能力比单纯背一个模板重要得多。

所以这道题叫“寄包柜”，名字起得很朴素，但思想含金量不低。接下来我展开讲三种能过的写法，以及它们各自的取舍。

3. 三种能AC的写法，我推荐你按这个顺序学

3.1 map<pair<int,int>, int>：最直观、最适合入门

第一种写法最贴近题目描述，直接把坐标包装成pair<int,int>作为键：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; map<pair<int, int>, int> box; while (q--) { int op, i, j; cin >> op >> i >> j; if (op == 1) { int x; cin >> x; box[{i, j}] = x; } else { auto it = box.find({i, j}); if (it == box.end()) { cout << -1 << '\n'; } else { cout << it->second << '\n'; } } } return 0; }

pair<int,int>可以直接作为map的键，因为标准库里已经实现了pair的小于号比较，红黑树需要依靠这个比较来维护有序性。这段代码的优点是几乎不需要思考，题目怎么描述就怎么翻译，特别适合刚学完 map 容器时用来建立“坐标到值”的映射直觉。

缺点也很明显：pair作为键会让代码稍微啰嗦一点，而且如果你以后想把map换成unordered_map提速，直接换会编译报错，原因是标准库没有给pair提供哈希函数。这就引出了第二种写法。

3.2 unordered_map 的坑：pair 没有默认哈希函数

很多人写完第一种之后会想：map 是红黑树，操作带 log，能不能换成 unordered_map，让查询变成平均 O(1)？

思路没问题，但直接这样写会失败：

unordered_map<pair<int, int>, int> box; // 编译报错，没有 hash<pair<int,int>>

原因是 C++ 标准库只为常见的内置类型、string 等类型提供了哈希函数，pair不在其中。解决方式是自己传一个哈希函数对象进去：

struct PairHash { size_t operator()(const pair<int, int>& p) const { return 1LL * p.first * 1000000007 + p.second; } }; unordered_map<pair<int, int>, int, PairHash> box;

这个自定义哈希的原理很简单：把两个 int 按照某个大质数混合成一个size_t。只要混合得别太差，实践中基本不会出问题。但说实话，为了一个入门题专门写一个哈希函数，有点小题大做。如果你更想直接用 unordered_map，我更推荐换一个思路，干脆不要用 pair 当键，而是把坐标压成一个整数。

3.3 把二维坐标压成一个 long long：位运算的通用做法

这类“二维坐标当键”的问题，最省心的做法是先把坐标整体压缩成一个long long。常见有两种方法。

第一种是线性公式：如果题目明确告诉你每个柜子有 m 个格子，所有柜子的格子数相同，那可以用key = (i - 1) * m + j。这个公式在行优先的二维数组里非常常见，坐标和编号一一对应。

但寄包柜这道题，很多版本的题面并没有给出一个统一的全局 m，每个柜子格子数可能不同。这时候如果再拿一个 m 去算，很容易错。更通用的做法是用位运算：把 i 放到高位，把 j 放到低位，组成一个不会冲突的长整数：

long long key = (1LL * i << 32) | j;

这里假设 i 和 j 都不超过 2^31，竞赛题里通常都满足。1LL * i先转成 long long，然后左移 32 位，给 j 留出足够空间，再用按位或放进去。这样得到的 key 可以放进unordered_map<long long, int>，不需要任何自定义哈希。

如果不用位运算，也可以选择一个大数作为偏移量，比如key = 1LL * i * 1000000000LL + j。前提是这个偏移量大于所有可能的 j。相比线性公式，位运算版本不依赖题面是否提供全局 m，适应性更好，我最终留下的是这一种。

3.4 三种方案对比与选型建议

我的建议是按顺序学：先用map<pair<int,int>, int>把题目语义理解透，知道“坐标到值”到底是怎么回事；然后试一下自定义哈希的写法，踩一踩编译报错的坑，你就理解为什么标准库没有给所有类型提供哈希函数；最后掌握位运算一维化，以后遇到二维状态压缩、稀疏矩阵、图论里点编号需要转成一维键的时候，都能直接套用。

4. 代码逐行拆解：从读入到输出的每一个细节

4.1 map<pair<int,int>, int> 完整代码

前面其实已经给出了一套能直接提交的代码，这里我再贴一遍并加注释，方便照着敲：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; map<pair<int, int>, int> box; while (q--) { int op, i, j; cin >> op >> i >> j; if (op == 1) { int x; cin >> x; box[{i, j}] = x; // 放入物品，覆盖旧值 } else { auto it = box.find({i, j}); if (it == box.end()) { cout << -1 << '\n'; // 从没放过东西 } else { cout << it->second << '\n'; } } } return 0; }

有些题解在查询时直接用cout << a[i][j]，因为 map 在键不存在时会默认构造一个 0 值。这样在这个题里有可能得到错误答案，因为你无法区分“查询的格子是空的”和“查询的格子放了物品 0”。题目要求空状态输出 -1，所以规范写法是先用find判断记录是否存在。

4.2 一维化 unordered_map 完整代码

我自己平时更常用的是这个版本，坐标压成 key 之后，容器只用存一个整数键，逻辑简单而且常数小：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; unordered_map<long long, int> box; box.reserve(q * 2); while (q--) { int op, i, j; cin >> op >> i >> j; long long key = (1LL * i << 32) | j; if (op == 1) { int x; cin >> x; box[key] = x; } else { auto it = box.find(key); if (it == box.end()) { cout << -1 << '\n'; } else { cout << it->second << '\n'; } } } return 0; }

这里box.reserve(q * 2)是提前告诉 unordered_map 大约会存多少个键，减少扩容带来的哈希搬移开销，后面第 5 章会展开讲。key的计算不需要担心 i 和 j 之间互相覆盖，因为位移给的位是完全分开的。

4.3 查询为什么优先用 find 而不是 []

我第一次写这类题的时候，很喜欢用box[key]直接取值，因为看起来简单。但[]有个隐藏行为：当键不存在时，它不会直接返回一个“空”给你，而是会往容器里插入一个键，并将值初始化为默认值（int 就是 0）。这会导致两个问题。

第一，查询时你没法区分“本来就没放过”和“确实存了 0”，只能额外加判断逻辑；第二，每个查询过的空键都会在容器里留下记录，白白增加容器大小，甚至触发 rehash。用find就不用担心这些，它只做查找，不会修改容器。

4.4 输出格式：一个换行符引发的 WA

这个细节看起来不起眼，但在真实评测里关系很大。题目要求每次查询单独占一行，漏掉换行符就会判 WA。我见过不少新手样例全对，交上去却 WA，最后发现只是输出格式问题。

另外，换行建议写'\n'而不是endl。endl本质是输出一个换行符，同时刷新输出缓冲区。刷缓冲区是有系统调用开销的，查询次数一旦到10^5量级，重复刷新带来的额外消耗就可能成为 TLE 的诱因。用'\n'既干净又高效。

5. 实测踩坑记录与两个低成本提速技巧

5.1 关了同步的 cin 还是被卡？直接换快读

我最初交的一版没有写ios::sync_with_stdio(false)，在数据量大的时候吃了一次 TLE。后来在开头加上这两行，cin 的速度基本能追上 scanf：

ios::sync_with_stdio(false); cin.tie(nullptr);

如果数据再狠一点，或者 OJ 的评测机性能不好，直接换一个 getchar 快读模板是最稳的。快读的原理很简单：用getchar逐字符读入，自己拼成整数，绕开标准输入流的格式化解析开销。

inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; }

凡是输入量达到10^5以上，用快读基本不会错。这个模板我平时一直放在本地的头文件里，遇到卡输入输出的题直接拿出来用。

5.2 一维化编号的两个经典错误

第一个错误是用了题面里不存在的全局 m。如果你拿到的题面明确说每个柜子有 m 个格子，那(i - 1) * m + j是正确公式；但寄包柜很多版本是“每个柜子格子数不一定相同”，根本没有全局 m 可用。这时硬套公式会发生坐标碰撞，两个不同的(i, j)算出同一个 key，查询结果就会错乱。

第二个错误更隐蔽：位运算时忘记加1LL。直接写i << 32，如果 i 是 int，左移 32 位的行为在 C++ 里是未定义的，而且高位早就被截断。正确写法是先转成 long long 再移位，也就是(1LL * i << 32) | j。这个 bug 在样例小数据上看不出来，因为 i 小的话，移位结果碰巧看起来正常，但数据一变大就崩。

5.3 空状态的查询别直接输出 0

如果你用cout << box[key]来查询，而某个格子从没被操作过，访问不存在的键时会插入一个默认值，输出的是 0，不是题目要求的 -1。这种情况很容易被忽略，因为整个程序运行正常，样例也可能不包含这种查询。

所以要养成习惯：涉及“查询键是否存在”的操作，一律用find判断迭代器是不是end()。这不仅能正确处理空状态，还能避免往容器里塞无意义的空记录。

5.4 reserve 和 max_load_factor：让哈希桶少 rehash

unordered_map 底层是一组哈希桶，元素数量超过桶数乘以负载因子时，它会自动扩容，把已有元素全部重新哈希一遍。这个过程不是免费的，操作次数多了以后会有可感知的开销。

如果你提前知道最多会产生大约多少条记录，可以在使用前给容器打声招呼：

box.reserve(q * 2); box.max_load_factor(0.7);

reserve会提前分配足够数量的桶，减少 rehash 频率；max_load_factor调低一些，哈希冲突更少，但占用内存会多一点。对于10^5级别数据量，这个优化带来的提升可能不是特别明显，但是在时间卡得很紧的题里，属于“写了一定不亏”的常规操作。

5.5 endl 真的很伤性能

这个知识点我在很多地方都提过，但每次自己写代码时还是会看到有朋友图省事用endl。endl和'\n'的区别在于，多了一个刷新输出缓冲区的动作。在循环里高频输出时，每输出一行刷新一次，会把很多时间浪费在系统调用上。

我实测过类似的题，同样一份代码，把cout << x << endl改成cout << x << '\n'，运行时间能明显下降。虽然寄包柜这道题可能两种写法都能过，但养成用'\n'的习惯，能让你在遇到更严格的评测时少一次 TLE。

最后说点我的体会。这道题代码量很小，但它把“数据结构先于算法”这件事体现得很清楚：拿到题先算数据规模，再选容器，比一上来就写模拟重要得多。寄包柜作为“深基15.例2”，恰好用最小的成本把“稀疏数据用字典按需存储”这个思想讲透了。如果你也在刷深基，我建议把 map 嵌套、自定义哈希、位运算一维化这三种写法都各敲一遍，尤其是最后一种。等你以后做二维状态压缩、稀疏矩阵或者需要给二维坐标统一编号的题时，会回来感谢这道例题的。