Rabbits

Problem Source

Original problem: P3939 Counting Colors

Hint: this is just a simple simulation. You may use fancy data structures, but you do not have to (some people really do overthink data structures).

Problem Background

The little fish-breeder raises many rabbits.

Problem Description

As everyone knows, rabbits are magical creatures with many fur colors.

The breeder has $n$ rabbits lined up from left to right, and the $i$-th rabbit has fur color $col_i$.

The rabbits are very active and often swap places with a neighbor.

The colorful rabbits dazzle the breeder, who wants to count the rabbits of a certain color in the interval $[l, r]$. His math is poor, so can you help him?

Input Format

The first line contains two positive integers $n, m$: the number of rabbits and the number of operations.

The second line contains $n$ positive integers $col_1, col_2, \dots, col_n$: the colors of the rabbits from left to right in the initial state.

The following $m$ lines each have the format 1 x or 2 l r c, where $\{1/2\}$ denotes the operation type.

• Operation $1$ is a swap: swap the positions of the $x$-th and the $(x+1)$-th rabbit.
• Operation $2$ is a query: ask how many rabbits of color $c$ are in the current interval $[l, r]$.

Output Format

For each operation $2$, output one line containing a natural number: the answer.

Sample Input

7 9
8 7 6 6 7 8 3
1 5
1 4
2 1 7 7
1 6
1 4
2 3 6 8
2 1 3 7
2 1 2 6
2 2 5 7

Sample Output

2
1
1
0
1

Constraints

$2 \le n \le 3 \times 10^5$, $1 \le m, col_i, c \le 3 \times 10^5$, and $1 \le x < n$, $1 \le l < r \le n$.