#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N=1e6+5,p=1e9+7;
int n,m,a[N],b[N],B,cnt,x,y,tot,pos[N],ne[N],tim,k,R,siz[N],ans[N];
char op;
struct node{
int l,r,t,id,k;
bool operator<(node &b) {
if (l/B!=b.l/B) return l<b.l;
if (r/B!=b.r/B) return r<b.r;
return t<b.t;
}
}s[N];
inline int rd() {
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
inline void add(int x,int v) {siz[x]+=v;}
int main() {
n=rd(),m=rd();
for (int i=1;i<=n;++i) a[i]=rd(),b[i]=a[i];
for (int i=1;i<=m;++i) {
op=getchar();
if (op=='C') {
x=rd(),y=rd();
ne[++cnt]=y;pos[++tim]=x;b[cnt+n]=y;
}else {
x=rd(),y=rd(),k=rd();
s[++tot].l=x,s[tot].r=y;s[tot].id=tot,s[tot].t=cnt;s[tot].k=k;
}
}
sort(b+1,b+n+cnt+1);
R=unique(b+1,b+n+cnt+1)-b-1;
for (int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+R+1,a[i])-b;
for (int i=1;i<=tim;++i) ne[i]=lower_bound(b+1,b+R+1,ne[i])-b;
B=pow(n,0.666);sort(s+1,s+tot+1);
for (int i=1,l=1,r=0,t=0;i<=n;++i) {
while(l>s[i].l) add(a[--l],1);
while(r<s[i].r) add(a[++r],1);
while(l<s[i].l) add(a[l++],-1);
while(r>s[i].r) add(a[r--],-1);
while(t<s[i].t) {
t++;
if (pos[t]>=l&&pos[t]<=r) {
add(a[pos[t]],-1);add(ne[t],1);
}swap(a[pos[t]],ne[t]);
}
while(t>s[i].t) {
if (pos[t]>=l&&pos[t]<=r) {
add(a[pos[t]],-1);add(ne[t],1);
}swap(a[pos[t]],ne[t]);
t--;
}
int k=lower_bound(b+1,b+R+1,s[i].k)-b;
ans[s[i].id]=siz[k];
}
for (int i=1;i<=tot;++i) write(ans[i]),puts("");
return 0;
}
评测记录