洛谷题单指南-线性表-P3613 【深基15.例2】寄包柜

原题链接：https://www.luogu.com.cn/problem/P3613

题意解读：此题很容易想成用二维数组求解，但是最多有10^5 * 10^5个寄包柜格子，二维数据会爆空间，题目明确各自一共不超过10^7，所以需要动态数据结构vector。

解题思路：

vector的问题在于需要提前明确空间大小，才能进行随即访问操作，否则可能导致下标越界，

这里就要用到一个重要的操作resize()，可以设定vector的数据长度，这样就保证了通过下标访问时不会越界。

100分代码：

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

const int N = 100005;

vector<int> a[N];
int n, q;

int main()
{
    cin >> n >> q;

    int op, i, j, k;
    while(q--)
    {
        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] << endl;
        }
    }

    return 0;
}