P3939 数颜色

题目描述

有 $n$ 个正整数$a_i$。

有 $m$ 次操作，每次操作为以下两种中的一种：

• “$1\ l_j\ r_j\ c_j$” ：询问在区间 $[l_j,r_j]$ 里有多少个值为 $c_j$ 的数；

• “$2\ x_j$”： $x_j$ 和 $x_j+1$ 两位置的值交换。

输入格式

第一行两个正整数 $n \ m \ (1 \le n,m \le 3 \times 10^5)$。

下来 $n$ 个正整数$a_i \ (1 \le a_i \le n)$。

下来 $m$ 行，每行为以下两种中的一种：

• $1\ l_j\ r_j\ c_j$

• $2\ x_j$

输出格式

对于每个 1 操作，输出一行一个正整数，表示答案。

输入输出样例 #1

输入 #1

6 5 
1 2 3 2 3 3  
1 1 3 2 
1 4 6 3  
2 3 
1 1 3 2  
1 4 6 3

输出 #1

1 
2 
2 
3

大样例