数颜色

数颜色( 二分(starstar ))

时限：(1s) 内存：(256M)

Descrption

小 (C) 的兔子不是雪白的，而是五彩缤纷的。每只兔子都有一种颜色，不同的兔子可能有相同的颜色。小 (C) 把她标号从 (1) 到(n)的(n)只兔子排成长长的一排，来给他们喂胡萝卜吃。排列完成后，第(i)只兔子的颜色是(a_i)。
俗话说得好，"萝卜青菜，各有所爱"。小 (C) 发现，不同颜色的兔子可能有对胡萝卜的不同偏好。比如，银色的兔子最喜欢吃金色的胡萝卜，金色的兔子更喜欢吃胡萝卜叶子，而绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求，小 (C) 十分苦恼。所以，为了使得胡萝卜喂得更加准确，小 (C) 想知道在区间([l_j,r_j])里有多少只颜色为(c_j)的兔子。
不过，因为小 (C) 的兔子们都十分地活跃，它们不是很愿意待在一个固定的位置；与此同时，小 (C) 也在根据她知道的信息来给兔子们调整位置。所以，有时编号为(x_j)和(x_{j+1})的两只兔子会交换位置。
小 (C) 被这一系列麻烦事给难住了。你能帮帮她吗？

Input

输入第 (1) 行两个正整数(n,m)。
输入第 (2) 行(n)个正整数，第(i)个数表示第(i)只兔子的颜色(a_i)。
输入接下来(m)行，每行为以下两种中的一种：
- (1 l_j r_j c_j) ：询问在区间([l_j,r_j])里有多少只颜色为(c_j)的兔子；
- (2 x_j)： (x_j)和(x_{j+1})两只兔子交换了位置

Output

对于每个 (1) 操作，输出一行一个正整数，表示你对于这个询问的答案

Sample Input

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

Sample Output

Hint

样例说明
- 前两个 (1) 操作和后两个 (1) 操作对应相同；在第三次的 (2) 操作后，(3) 号兔子和 (4) 号兔子交换了位置，序列变为 (1 2 2 3 3 3)。
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。
- 对于所有测试点，有$1leq l_j leq r_j leq n , 1 leq x_j leq n $
- 每个测试点的数据规模及特点如下表：
特殊性质 1：保证对于所有操作 1，有(|r_j - l_j| leq 20) 或　(|r_j - l_j| geq n-20)
特殊性质 2：保证不会有两只兔子相同颜色的兔子。
来源：(luogup3939)

分析

我们可以用类似的桶记录下某一个颜色出现的位置，然后查询 ([l,r]) 颜色 (x) 出现几次，我们可以二分找到 (l) 在桶中的位置，(r) 在桶中的位置，则个数即为两个位置之差。
交换也相对比较简单，当 (a[i]==a[i+1]) 时不用交换，当不等时，在各自的桶值把位置修改下，然后再把两个 (a[i],a[i+1]) 交换下即可。

Code

#include <bits/stdc++.h>
const int maxn=3e5+5;
std::vector<int> q[maxn];
int n,m,a[maxn];
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q[a[i]].push_back(i);
	}
}
void Solve(){
	int l,r,opt,x;
	while(m--){
		scanf("%d",&opt);
		int pos_l,pos_r;
		if(opt==1){
			scanf("%d%d%d",&l,&r,&x);
			pos_l=std::lower_bound(q[x].begin(),q[x].end(),l)-q[x].begin();
			pos_r=std::upper_bound(q[x].begin(),q[x].end(),r)-q[x].begin()-1;
			if(pos_r<pos_l)//区间没有x时，pos_r比pos_l少1
				printf("0
");
			else
				printf("%d
",pos_r-pos_l+1);
		}
		else{
			scanf("%d",&x);
			if(a[x]==a[x+1])continue;
			pos_l=std::lower_bound(q[a[x]].begin(),q[a[x]].end(),x)-q[a[x]].begin();
			q[a[x]][pos_l]++;
			pos_r=std::lower_bound(q[a[x+1]].begin(),q[a[x+1]].end(),x+1)-q[a[x+1]].begin();
			q[a[x+1]][pos_r]--;
			std::swap(a[x],a[x+1]);
		}
	}
}
int main(){
	Init();
	Solve();
	return 0;
}

数颜色

数颜色( 二分(starstar ))

样例说明