题目链接：P3613 【深基15.例2】寄包柜 - 洛谷 | 计算机科学教育新生态
难度：普及
题目分析：观察题目要求，很容易想到用二维数组来解决这个问题。但真就这么简单的 AC了吗？
如果真这么简单就好了，开一个数组a[1e5][1e5]空间复杂度是1e5 * 1e5 * 4(字节）约等于40gb而题目要求是128mb。
所以我们可以用一个vector来解决。那vector怎么用呢，有以下几种常用的操作：
（1）vector a 定义一个int类型的vector一维数组。
（2）vector a(10) 定义一个int类型的长度为十的vector一维数组。
（3）vector a(10)(1) 定义一个int类型的长度为十初值为一的vector一维数组。
（4）vector<vector > a 定义一个int类型的vector二维数组，要注意的是，在里面的vecotr后面要加一个空格，否则会被认为是移位运算符而编译错误。
（5）a.begin() 返回数组a的首元素的指针（迭代器）。
（6）a.end() 返回数组a的末尾元素的下一个元素的指针（迭代器）。
（7）a.size() 数组中的元素个数
（8）a.empty() 判断数组是否为空
（9）a.clear() 清空数组中的元素
（10）a.insert(a.begin(),1000) 将1000插入到向量a的起始位置前
（11）a.insert(a.begin(),3,1000); 将1000分别插入到向量元素位置的0-2处(共3个元素)
（12）a.erase(a.begin()); 将起始位置的元素删除
（13）a.erase(a.begin(),a.begin()+3) ; 将(a.begin(),a.begin()+3)之间的元素删除
（14）a.push_back(1) 将1放到数组尾部
vector和数组相比，vector可以改变长度，清空的时间复杂度为O(1)。
下面奉上代码：
#include<bits/stdc++.h>//万能头文件
using namespace std;
typedef long long ll;
int n,q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
vector<vector<int> >a(n + 1);// 一共有0到n个柜子
while(q--)
{
int i,j,k;
int op;
cin >> op;
if(op == 1)
{
cin >> i >> j >> k;
if(a[i].size() < j + 1){//如果不够大就扩容
a[i].resize(j + 1);
}
a[i][j] = k;
}
else
{
cin >> i >> j;
cout<<a[i][j]<<'\n';
}
}
return 0;
}
接下来接受STL中map的做法（STL 中有一种叫做 mapmap 的数据结构，可以将两个变量之间建立映射关系）
常见函数：
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
erase() 删除一个元素
find() 查找一个元素
insert() 插入元素
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
最后奉上代码：
#include<bits/stdc++.h>//万能头文件
using namespace std;
typedef long long ll;
const int N = 1 * 1e5 + 10;//宏定义
map<int,int>mp[N];
int n,q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
while(q--)
{
int i,j,k;
int op;
cin >> op;
if(op == 1)
{
cin >> i >> j >> k;
mp[i][j] = k;
}
else
{
cin >> i >> j;
cout<<mp[i][j] <<'\n';
}
}
return 0;
}