計算數字個數 1

給你 \(N\) 個正整數序列 \(a_1, a_2, \ldots, a_N\)，接著再給你 \(Q\) 個詢問，第 \(i\) 個詢問給你一個正整數 \(b_i\)，請回答 \(b_i\) 在序列 \(a\) 中出現幾次。

本題想讓大家練習用陣列記錄每個數字出現幾次，所以評測會檢查你的原始碼，禁止使用 C/C++ 標準函式庫的關聯容器，包含 set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、unordered_multimap。違反限制會得到 Wrong Answer，回饋訊息會顯示「語法限制未通過」。

以下範例程式碼會因效率不足，只能通過較小的測試資料。

#include<iostream>
using namespace std;
const int MAX_N = 200000;
int main() {
    int a[MAX_N];
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> a[i];
    int Q;
    cin >> Q;
    while(Q--) {
        int b;
        cin >> b;
        int ans = 0;
        for(int i = 0; i < N; i++) ans += (a[i] == b);
        cout << ans << endl;
    }
    return 0;
}

輸入格式

輸入第一行包含一個正整數 \(N\)，第二行包含 \(N\) 個正整數 \(a_1, a_2, \ldots, a_N\)。

接著第三行包含一個正整數 \(Q\)，第四行包含 \(Q\) 個正整數 \(b_1, b_2, \ldots, b_Q\)。

限制

• \(1 \le N \le 2 \times 10^5\)
• \(1 \le a_i \le 10^6\)
• \(1 \le Q \le 2 \times 10^5\)
• \(1 \le b_i \le 10^9\)

輸出格式

共輸出 \(Q\) 行，第 \(i\) 行包含一個整數代表第 \(i\) 個詢問的答案。

評分說明

共有 \(3\) 個子題，每個子題包含多組測試資料，一個子題的測試資料全部答對才能得到該子題的分數。

各子題的配分及額外限制如下：

• 子題 \(1\)：\(2\) 分，\(N, Q \le 5000, b_i \le 10^6\)。
• 子題 \(2\)：\(2\) 分，\(b_i \le 10^6\)。
• 子題 \(3\)：\(1\) 分，無額外限制。

範例輸入

5
1 3 1 4 520
7
1 2 3 4 100000 1000000000 7

範例輸出

2
0
1
1
0
0
0

範例解釋

\(1\) 在序列中出現 \(2\) 次，\(3\) 和 \(4\) 各出現 \(1\) 次，其餘詢問的數字都沒有出現，所以答案依序是 \(2, 0, 1, 1, 0, 0, 0\)。

此題時限設置得非常緊，若要通過，請一定要使用 I/O 優化，也就是說，請在程式碼讀入任何東西之前，加入以下兩行：

cin.tie(0);
ios_base::sync_with_stdio(false);

並且換行必須使用 \n，若使用 endl 也會超時。