rt,只对了9和10

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
const int N=1e6+5;
struct Segment_tree{
	int l,r;
	int sum;
}t[N<<5];
struct node{
	int a,b,c;
}ask[N];
int n,m,a[N],Rank[N],len,cnt,pos,nope,dis[N],tot[N],root[N];
char str[N];
void update(int &rt,int l,int r,int x,int k){
	if(!rt)rt=++cnt;
	if(l==r){
		t[rt].sum+=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(t[rt].l,l,mid,x,k);
	else update(t[rt].r,mid+1,r,x,k);
}
void add(int l,int k){
	for(int i=l;i<=n;i+=lowbit(i)){
		update(root[i],1,len,a[l],k);
	}
}
int Query(int l,int r,int k){
	if(l==r){
		int sum=0;
		for(int i=1;i<=pos;i++)sum+=t[dis[i]].sum;
		for(int i=1;i<=nope;i++)sum-=t[tot[i]].sum;
		return sum;
	}
	int mid=(l+r)>>1;
	if(k<=mid){
		for(int i=1;i<=pos;i++)dis[i]=t[dis[i]].l;
		for(int i=1;i<=nope;i++)tot[i]=t[tot[i]].l;
		return Query(l,mid,k);
	}
	else {
		for(int i=1;i<=pos;i++)dis[i]=t[dis[i]].r;
		for(int i=1;i<=nope;i++)tot[i]=t[tot[i]].r;
		return Query(mid+1,r,k);
	}
}
int Find(int l,int r,int k){
	pos=nope=0;
	for(int i=r;i>0;i-=lowbit(i))dis[++pos]=root[i];
	for(int i=l-1;i>0;i-=lowbit(i))tot[++nope]=root[i];
	return Query(1,len,k);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],Rank[i]=a[i];
	len=n;
	for(int i=1;i<=m;i++){
		cin>>str[i]>>ask[i].a>>ask[i].b;
		if(str[i]=='C')Rank[++len]=ask[i].b;
		else cin>>ask[i].c;
	}
	sort(Rank+1,Rank+n+1);
	len=unique(Rank+1,Rank+len+1)-Rank-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(Rank+1,Rank+len+1,a[i])-Rank;
		add(i,1);
	}
	for(int i=1;i<=m;i++){
		if(str[i]=='C'){
			add(ask[i].a,-1);
			a[ask[i].a]=lower_bound(Rank+1,Rank+len+1,ask[i].b)-Rank;
			add(ask[i].a,1);
		}
		else{
			cout<<Find(ask[i].a,ask[i].b,ask[i].c)<<endl;
		}
	}
	return 0;
}