#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],idx;
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[++idx]=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[++idx]=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;b[++idx]=k;
        }
    }
    sort(b+1,b+idx+1);
    R=unique(b+1,b+idx+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<=tot;++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;
}

评测记录