静态区间元素出现次数

【题目描述】

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \ldots, a_{N-1}$。依次处理以下 $Q$ 个查询：

• $l$ $r$ $x$：输出 $x$ 在 $a_{l}, a_{l+1}, \ldots, a_{r-1}$ 中出现的次数。

【输入】

$N$ $Q$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$l_0$ $r_0$ $x_0$
$l_1$ $r_1$ $x_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$ $x_{Q-1}$

【输出】

对每个查询，输出一行一个整数，表示 $x$ 在 $a_l, a_{l+1}, \ldots, a_{r-1}$ 中出现的次数。

【输入样例】

5 3
3 7 1 2 1
1 5 1
3 3 0
0 4 3

【输出样例】

2
0
1

【数据范围】

• $0 \leq N \leq 500000$
• $0 \leq Q \leq 500000$
• $0 \leq a_i \leq 1000000000$
• $0 \leq l \leq r \leq N$
• $0 \leq x \leq 1000000000$

【来源】

Library Checker（yosupo06） static_range_frequency