【深基15.例2】寄包柜

题意

有很多寄包柜，每个柜子的格子上界未知。支持给 (柜子,格子) 写入物品编号，以及查询该位置的物品。

思路

格子编号可能很大，但操作总数只有 10^5，没有必要为每个柜子开到最大编号。

建立 lockers[i] 字典，只记录第 i 个柜子实际写入过的 cell -> item。写入和查询都直接使用两次下标，期望 $O(1)$ 完成。

Python 知识

[dict() for _ in range(n+1)] 为每个柜子创建独立字典；不能写 [{}]*(n+1)，否则所有柜子会共享同一个字典。
lockers[locker][cell]=item 直接表达二维稀疏映射。
操作行长度不同，按行读取后解包比整份 token 更直观。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：dict 键值映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：可变容器不能用乘法复制。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import sys


input = sys.stdin.buffer.readline
n, query_count = map(int, input().split())
lockers = [dict() for _ in range(n + 1)]
answers = []

for _ in range(query_count):
    operation = list(map(int, input().split()))
    if operation[0] == 1:
        _, locker, cell, item = operation
        lockers[locker][cell] = item
    else:
        _, locker, cell = operation
        answers.append(str(lockers[locker][cell]))

print("\n".join(answers))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * P3613 【深基15.例2】寄包柜
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXQ = 100005;

// 每个柜子用链表存（格子→物品）
// head[i] 指向柜子 i 的链表头
// to[cnt] 格子编号, val[cnt] 物品编号, nxt[cnt] 下一条
int head[MAXN], to[MAXQ], val[MAXQ], nxt[MAXQ];
int cnt = 0;

// 向柜子 locker 的链表头部插入 (格子,物品)
void add(int locker, int cell, int item) {
    ++cnt;
    to[cnt] = cell;
    val[cnt] = item;
    nxt[cnt] = head[locker];
    head[locker] = cnt;
}

// 查询柜子 locker 中格子 cell 上的物品
int query(int locker, int cell) {
    for (int i = head[locker]; i; i = nxt[i]) {
        if (to[i] == cell) return val[i];
    }
    return -1; // 题目保证查询都存在，不会走到这里
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    while (q--) {
        int op, locker, cell;
        scanf("%d%d%d", &op, &locker, &cell);
        if (op == 1) { // 写入
            int item;
            scanf("%d", &item);
            add(locker, cell, item);
        } else { // 查询
            printf("%d\n", query(locker, cell));
        }
    }
    return 0;
}

复杂度

每次操作期望 $O(1)$ ，总空间与不同的实际写入格子数成正比，最坏 $O(q)$ 。

总结

面对巨大但稀疏的二维编号空间，字典只存出现过的位置，通常比按最大下标开二维数组更自然。

【深基15.例2】寄包柜

目录

题意

思路

Python 知识

代码

复杂度

总结