题目背景
鶸尛鱻养了许多兔纸。
题目描述
众所周知,兔纸是一种神奇的生物,它有许多种毛色。
鶸尛鱻一共有 $n$ 只兔纸,它们从左到右排成一排,第 $i$ 只兔纸的毛色为 $col_i$。
兔纸们十分活跃,时常会与旁边的兔纸交换位置。
五颜六色的兔纸弄得鶸尛鱻眼花缭乱,他想统计区间 $[l, r]$ 内兔纸的颜色,但他的数学很差,你可以帮帮他吗?
输入格式
第 $1$ 行两个正整数 $n, m$ 分别表示兔纸数量和操作次数。
第 $2$ 行 $n$ 个正整数 $col_1, col_2, \dots, col_n$,表示初始状态下从左到右每只兔纸的颜色。
此后 $m$ 行,每行输入格式为 1 x
或 2 l r c
,其中 $\{1/2\}$ 表示操作类型。
操作 $1$ 为 交换 操作,表示第 $x$ 只兔纸和第 $x + 1$ 只兔纸交换位置。
操作 $2$ 为 查询 操作,询问当前区间 $[l, r]$ 内有多少只颜色为 $c$ 的兔纸。
输出格式
对于每个操作 $2$,你需要输出一行一个自然数作为答案。
样例输入
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
样例输出
2
1
1
0
1
数据范围
对于全部测试数据,满足 $2 \le n \le 3 \times 10^5$,$1 \le m, col_i, c \le 3 \times 10^5$,且保证 $1 \le x < n$,$1 \le l < r \le n$。
附加说明
原题:P3939 数颜色
提示:这只是个简单的模拟,虽然可以使用复杂的数据结构,但没必要。(肯定有人学数据结构学傻了)