题解 P3613 【【深基15.例2】寄包柜】

· · 题解

Update on 2020.8.10：修改了题解中的一些累赘部分

Update on 2022.8.4：修改题解做法，确保复杂度正确

首先我们期望的一个强大的数组应该存放这个三个元素：第 i 个柜子的第 j 个格子以及存入的物品 k 。那么怎么去实现呢？

第一个想到的肯定是二维数组，但是看下数据范围：1\le n\le 10^5，1 \le a_i \le 10^5，并且有已知超市里共计不会超过 10^7 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。因此设置一个数组 \texttt{a[100005][100005]} 就肯定 \texttt{MLE} 了，所以这个方法就别想了。

挑战 \texttt{MLE}

怎样设置数组才能节省内存呢？我们想到动态数组 \texttt{vector}，尝试一下吧！设置一个结构体 \texttt{desk} ,里面有三个参数，如下：

const int MAX = 100005;
struct node
{
    //s用来记录desk[i]的元素个数，表示第i个柜子已存s次物品 
    //num表示第i个柜子的第num个格子存入一个物品
    //w表示该格子存入的物品 
    vector<int> num,w;//用vector动态数组节省内存，以防MLE 
    int s = 0;
} desk[MAX];

接下来处理输入，若是寄存操作，那么我们只要把该个柜子的存放次数 +1，并把 num,w (即格子编号和物品)存入动态数组中即可。

desk[a].s++; //第a个柜子存入物品
desk[a].num.push_back(b);//第b个格子中 
desk[a].w.push_back(c);//存入物品c

再来看查询操作，由题可知操作保证合法，所以直接查询就可以了。那么应该怎么循环呢？很简单，查找 \texttt{a} 柜子，然后从后往前循环。因为后面的元素可能与之前重复，说明该柜子的某个格子存放的物品有更新。

因此就有：

for(int i = desk[a].s - 1;i >= 0;i--)//从后往前，因为格子存放会有更新 
{
    if(desk[a].num[i] == b)//如果查询到该柜子的格子 
    {
        cout<<desk[a].w[i]<<endl;//输出该格子内的物品 
        break;//因此时是最新的存放情况，所以有解后需要直接退出查询 
        //提醒：break 很重要，不能遗漏，否则一次查询就可能输出多解。
    }
}

看起来是个不错的实践，由于数据较弱，似乎能过，但仔细分析一下复杂度，发现是 O(n^2)的,看来这个思路并不可行。

挑战 \texttt{TLE}

于是又想到了强大的 map 库，定义 map <pair <int,int>,int> p 来表示，p[{i,j}] 表示第 i 个柜子的第 j 个格子的物品。对于每一个操作 1，直接赋值即可，p[{i,j}] = k；对于而操作，直接输出 p[{i,j}]。

于是乎，我们得到了最终复杂度正确的算法，代码如下：

#include <cstdio>
#include <map>
using namespace std;
inline int read ();
int n,q; 
map <pair <int,int>,int> p;
int main ()
{
    n = read ();q = read ();
    while (q--)
    {
        int ty = read ();
        if (ty == 1) p[{read (),read ()}] = read ();
        else printf ("%d\n",p[{read (),read ()}]);
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}