题解 P3613 【【深基15.例2】寄包柜】
linponess
·
·
题解
观察题目要求，很容易想到用二维数组来解决这个问题。
但真就这么简单的 AC 了吗？
一个OI选手的直觉告诉我们没有！！！
仔细观察，发现我们要使用数组的话，需要开一个 10^5*10^5 的数组，这会导致空间复杂度爆炸致死， OUT!
再次观察数据范围，发现最多只会有 10^7 个寄包格子，有大量的空间被浪费了。
如何减小空间复杂度？
可以使用动态的数据结构，如链表，定义一个链表结构体便可以解决空间复杂度爆炸的问题。
但真就这么简单的 AC 了吗？
一个OI选手的直觉告诉我们没有！！！
再次仔细观察数据范围，发现最多会有 10^5 次查询操作，因为链表查找时间复杂度过劣，最高时间复杂度高达 10^7*10^5 ，TLE 到直接自闭，OUT!
如何减小时间复杂度？
开数组。
有没有一种办法能将以上两种方法结合起来，使其兼有两种方法的优点呢？
众所周知动态数据结构不止一种那你还提什么链表，尤其是 STL 中给我们提供了许多好用又方便的动态数据结构，比如下面这位老大哥：vector。
一点都不轻松好吧！下标是连续分配的，根本不能利用下标来查询。~~你个大骗子，浪费我们时间！~~
但真的是这样吗？考虑到空间下标是稀疏的，我们可以用 离~散~化~ 来压缩下标，成功解决下标问题。
但真就这么简单的 $AC$ 了吗？
~~诶诶诶，不要打我好吗，我这叫循序渐进地讲题。~~
没错，你真的 $AC$ 了~~不骗你~~，可喜可贺，可喜可贺。
~~完结撒花。~~
------------
但让我们拓展一下，如果题目要求强制在线，离散化不可用怎么办？
这就需要我们另寻他法压缩下标，这里介绍一个好东西叫做哈希，其核心理念就是通过一个函数来把字符串或数字压缩到一个较小的范围内，至于实现方法~~请读者自证~~请读者另寻其他文章，luogu上有哈希的模板题，题解区应该有不少文章比我写得好，我在这里就不说了。
但就没有更优的解决方法了吗？
~~一个OI选手的直觉告诉我们必须有！！！~~
让我们稍微回顾下前情：
>众所周知动态数据结构不止一种
~~是的，我就是瞒着更好用的动态数据结构没告诉你。~~
$STL$ 中有一种叫做 $map$ 的数据结构，可以将两个变量之间建立映射关系~~不知道映射的请自行百度~~，也就是说，它的下标可以是**任意的数据类型**~~字符串、负数、实数什么都行~~，岂不比手打哈希好得多（$map$ 实际上就是 $STL$ 的哈希，但据说手打哈希常数要比 $map$ 要小，不知真伪，如有能提供证据者请私信我）？
但题目数据是二维的，如何解决这个问题？
可以手打结构体（由于是 $STL$ 你还得重载运算符，异常麻烦），或用 $make\_pair$ 法，由于这两种方法比较难懂，我在这里就不讲了，请读者自行查阅资料。
但由于两维数据都在 $10^5$ 的范围内，我们可以通过一些比较玄妙的方法，将一维数据乘上 $10^5$ 再加上另一维数据，把两个 $int$ 类型的数据压成一个 $long\ long$ 类型的数据，本人在比赛中使用的就是这种方法。
以下是代码：
```cpp
#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{
scanf("%d%d",&n,&q);
while(q--)
{
scanf("%d%d%d",&p,&i,&j);
if(p==1)
{
scanf("%d",&k);
b[i*1000000+j]=k;
}
else printf("%d\n",b[i*1000000+j]);
}
return 0;
}
```
或者我们用一些更简单的方法，比如：开一个 $map$ 数组（虽说是动态的，但开得过大仍有爆栈的可能）。
------------
二次拓展：如果数据范围大于 $long\ long$ 怎么办？
解决方案：使用字符串读入。
三次拓展：如果数据有 $N$ 维，又害怕数组开得过大爆栈怎么办？
解决方案：把 $N$ 个字符串并为一个字符串。
$\huge\mathbb{END.}