收藏统计

题目描述:

      WXY是一个喜欢收藏乌龟的同学，他收藏的乌龟都有不同的颜色（别问我为啥），其中，第i只乌龟的颜色为C_i。WXY也很喜欢摆弄他的乌龟，每次都可以把第i（1≤i<n）只乌龟和第i+1只乌龟互换位置。WXY是一个求知欲很强的同学，他想知道一些操作过后，从编号L到R之中有几只乌龟颜色为C₀。

输入格式:

第一行两个整数n，m。分别表示有n只乌龟，操作数量加询问数量为m；

第二行n个整数C_i表示第i只乌龟的颜色。

第三行到第m+2行，第一个数若为1，后跟L，R，C₀，意义如题。若为2，后跟一个整数i（1≤i<n），表示交换第i只和第i+1只乌龟。

输出格式:

有多少个询问就有多少行输出，对于每个询问，输出在区间[L,R]间有多少只乌龟颜色为C0。

样例输入:

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
2
2
3

提示:

对于30%的数据，1<=n<=1000,1<=m<=2000,1<=a_i<=10^4

对于60%的数据，1<=n<=5*10^4,1<=m<=10^5,1<=ai<=10^4

对于100%的数据，1<=n,ai<=3*10^5,m<=6*10^5

本题数据由zhr生成，未经允许，不得纂改！

时间限制: 1000ms
空间限制: 256MB

---

来源: by zhr