传送门
本来出题人出出来想考数据结构的。
但是我们拥有map+vector/set这样优秀的STL，因此直接用map离散化，vector存下标在里面二分找答案就行了。
代码：
#include<bits/stdc++.h>
#define N 100005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(int x){
if(x>9)write(x/10);
putchar((x%10)^48);
}
int n,m,x,tot=0,cnt=0,num[N];
map<int,int>mp;
vector<int>pos[N<<1];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
num[i]=read();
if(!mp[num[i]])mp[num[i]]=++tot;
pos[mp[num[i]]].push_back(i);
}
while(m--){
char op[2];
scanf("%s",op);
int a=read(),b=read();
if(op[0]=='Q'){
int c=read();
vector<int>::iterator l=lower_bound(pos[mp[c]].begin(),pos[mp[c]].end(),a);
vector<int>::iterator r=lower_bound(pos[mp[c]].begin(),pos[mp[c]].end(),b);
if(l==pos[mp[c]].end()){puts("0");continue;}
printf("%d\n",r-l+(*r==b));
}
else{
if(num[a]==b)continue;
if(!mp[b])mp[b]=++tot;
pos[mp[num[a]]].erase(lower_bound(pos[mp[num[a]]].begin(),pos[mp[num[a]]].end(),a));
pos[mp[b]].insert(lower_bound(pos[mp[b]].begin(),pos[mp[b]].end(),a),a);
num[a]=b;
}
}
return 0;
}