【哈希3】前缀查询问题

前言

在解决需要频繁查询元素出现次数的问题时，哈希表（Hash Table）是一种高效的数据结构。前面我们已经详细介绍了哈希表的基本使用方法，此处将继续探讨其在前缀查询问题中的应用。

哈希表相关介绍

题解

题目描述

给定一个长度为 $n$ 的数组 $a$，数组中的每个元素都是正整数。我们需要回答 $n$ 个查询，第 $i$ 个查询是关于数组前缀 $a_1, a_2, ..., a_i$ 的：

对于每一个查询 $i$，请你计算在前缀 $a_1, a_2, ..., a_i$ 中数字 $i$ 出现了多少次。

输入描述

第一行包含一个整数 $n$ ($1 \leq n \leq 10^{5}$)，表示数组的长度。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$)，表示数组 $a$。

输出描述

输出 $n$ 个整数，第 $i$ 个整数表示数字 $i$ 在前缀 $a_1, a_2, ..., a_i$ 中出现的次数。

样例1

输入

5
1 2 1 3 2

输出

1 1 0 0 0

样例解释

前缀 [1] 中，数字 1 出现 1 次。

前缀 [1, 2] 中，数字 2 出现 1 次。

前缀 [1, 2, 1] 中，数字 3 出现 0 次。

前缀 [1, 2, 1, 3] 中，数字 4 出现 0 次。

前缀 [1, 2, 1, 3, 2] 中，数字 5 出现 0 次。