/*
 * 演算法 / Algorithm:
 * 與 C 版本相同：用一個 vector<int> freq 當作共用頻率表，
 * 每加入 A[i]、B[i] 後檢查是否從 1 變 2，若是就把 common 加一。O(n) 時間。
 * Same idea as the C version, using STL vector. Each 1->2 transition adds one to common.
 */

#include <vector>     // 提供 std::vector / Provides std::vector
using namespace std;  // 省略 std:: 前綴（教學用，正式專案通常避免）/ drop std:: prefix for readability

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();                           // n 是陣列長度 / length of A (and B)

        // vector<int>(n+1, 0) 建立長度 n+1、全為 0 的向量；
        // 因為題目值的範圍是 1..n，我們以值本身當索引，所以多開一格。
        // Counter indexed by value; values are 1..n, so size n+1.
        vector<int> freq(n + 1, 0);

        vector<int> result(n);                      // 結果向量，預設都是 0；我們會逐一覆寫 / result vector, will be overwritten
        int common = 0;                             // 已知兩邊都出現過的數字個數 / running count

        for (int i = 0; i < n; i++) {               // range-for 也可以，但用索引比較清楚 / index loop keeps things explicit
            // ++freq[A[i]] 是「先加一，再取值」(前置遞增) / pre-increment: add 1 first, then read the new value
            if (++freq[A[i]] == 2) common++;        // 若加完正好等於 2，代表 A、B 都出現過 / 1->2 means seen in both prefixes
            if (++freq[B[i]] == 2) common++;        // 對 B[i] 同樣處理 / same check for B[i]

            result[i] = common;                     // 寫入答案 / store answer
        }

        return result;                              // C++ 回傳 vector，記憶體由 STL 管理 / STL handles memory, just return by value
    }
};