8845: [yosupo] Data Structure - Static Range Frequency
[Creator : ]
Description
You are given an integer sequence $a_0, a_1, \ldots, a_{N-1}$ with the length $N$. Process the following $Q$ queries in order:
- $l$ $r$ $x$ : Print the number of times $x$ occurs in $a_{l}, a_{l+1}, \ldots, a_{r-1}$.
- $l$ $r$ $x$ : Print the number of times $x$ occurs in $a_{l}, a_{l+1}, \ldots, a_{r-1}$.
Input
$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}$
$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}$
Constraints
$0 \leq N \leq 500000$
$0 \leq Q \leq 500000$
$0 \leq a_i \leq 1^9$
$0 \leq l \leq r \leq N$
$0 \leq x \leq 10^9$
$0 \leq Q \leq 500000$
$0 \leq a_i \leq 1^9$
$0 \leq l \leq r \leq N$
$0 \leq x \leq 10^9$
Sample 1 Input
5 3
3 7 1 2 1
1 5 1
3 3 0
0 4 3
Sample 1 Output
2
0
1