11258: [yosupo] Data Structure - Point Set 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:
- `0 $k$ $v$`: $a[k] \gets v$
- `1 $l$ $r$ $x$` : Print the number of times $x$ occurs in $a_{l}, a_{l+1}, \ldots, a_{r-1}$.
- `0 $k$ $v$`: $a[k] \gets v$
- `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}$
$\mathrm{query}_0$
$\vdots$
$\mathrm{query}_{Q-1}$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$\mathrm{query}_0$
$\vdots$
$\mathrm{query}_{Q-1}$
Constraints
- $0 \leq N \leq 2\times 10^5$
- $0 \leq Q \leq 2\times 10^5$
- $0 \leq a_i \leq 10^9$
- $0 \leq k < N$
- $0 \leq v \leq 10^9$
- $0 \leq l \leq r \leq N$
- $0 \leq x \leq 10^9$
- $0 \leq Q \leq 2\times 10^5$
- $0 \leq a_i \leq 10^9$
- $0 \leq k < N$
- $0 \leq v \leq 10^9$
- $0 \leq l \leq r \leq N$
- $0 \leq x \leq 10^9$
Sample 1 Input
5 6
3 7 1 2 1
1 1 5 1
1 3 3 0
1 0 4 3
0 1 1
1 0 5 1
1 0 5 123456789
Sample 1 Output
2
0
1
3
0