题目分析：
解法一：
显然我们可以直接对每一种颜色建一棵线段树，然后剩下的操作就非常简单了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int tot,col[N],lson[100*N],rson[100*N],sum[100*N],rt[N];
void modify(int &now,int now_l,int now_r,int pos,int val){
if(!now) now = ++tot;
if(now_l == now_r){
sum[now] += val;
return;
}
int mid = (now_l + now_r)>>1;
if(pos <= mid) modify(lson[now],now_l,mid,pos,val);
if(pos > mid) modify(rson[now],mid+1,now_r,pos,val);
sum[now] = sum[lson[now]] + sum[rson[now]];
}
int query(int now,int now_l,int now_r,int l,int r){
if(!now) return 0;
if(l <= now_l && r >= now_r) return sum[now];
int mid = (now_l + now_r)>>1,ans = 0;
if(l <= mid) ans = ans + query(lson[now],now_l,mid,l,r);
if(r > mid) ans = ans + query(rson[now],mid+1,now_r,l,r);
return ans;
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%d",&col[i]);
modify(rt[col[i]],1,n,i,1);
}
for(int i=1; i<=m; i++){
int opt,x,y,z;
scanf("%d",&opt);
if(opt == 1){
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",query(rt[z],1,n,x,y));
}
else{
scanf("%d",&x);y = x + 1;
modify(rt[col[x]],1,n,x,-1);modify(rt[col[y]],1,n,y,-1);
modify(rt[col[x]],1,n,y,1);modify(rt[col[y]],1,n,x,1);
swap(col[x],col[y]);
}
}
return 0;
}
解法二：
（大型学数据结构学傻系列）
我们其实可以考虑直接用数组储存每一种颜色出现的位置，对于查询操作就直接二分就好了。
之所以可以这样做，因为我们每一次交换位置都是交换的 \(x\) 与 \(x+1\)，当它们的颜色不同时，交换是不会影响数组内的单调性的，所以就可以直接这样做了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
vector<int> v[N];
int a[N];
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
v[a[i]].push_back(i);
}
for(int i=1; i<=m; i++){
int opt,x,y,z;scanf("%d",&opt);
if(opt == 1){
scanf("%d%d%d",&x,&y,&z);
int t1 = lower_bound(v[z].begin(),v[z].end(),x) - v[z].begin();
int t2 = upper_bound(v[z].begin(),v[z].end(),y) - v[z].begin() - 1;
printf("%d\n",t2 - t1 + 1);
}
else{
scanf("%d",&x);y = x + 1;
if(a[x] == a[y]) continue;
int t1 = lower_bound(v[a[x]].begin(),v[a[x]].end(),x) - v[a[x]].begin();
int t2 = lower_bound(v[a[y]].begin(),v[a[y]].end(),y) - v[a[y]].begin();
swap(v[a[x]][t1],v[a[y]][t2]);
swap(a[x],a[y]);
}
}
return 0;
}