RT，本人在vjudge上提交，开O2tle

思路：线段树维护区间质数，区间赋值，区间查询等操作

Code：

#include<iostream>
using namespace std;
long long tree[400005],tag[400005],tree2[400005],tag2[400005],sz[100005],a[10000005],b[800005],treepr[100005],num[100005],n,r;
void shai(int n){
	a[0]=a[1]=1;
	for(int i=2;i<=n;i++){
		if(!a[i]){
			b[++r]=i;
		}
		for(int j=1;j<=r&&i*b[j]<=n;j++){
			a[i*b[j]]=1;
			if(i%b[j]==0){
				break;
			}
		}
	}
}
void psup(int x){
	tree[x]=tree[x<<1]+tree[x<<1|1];
	tree2[x]=tree2[x<<1]+tree2[x<<1|1];
}
void build(int now,int l,int r){
	if(l==r){
		if(sz[l]>=1&&sz[l]<=1e7){
			tree[now]=!a[sz[l]];
		} 
		tree2[now]=sz[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	psup(now);
}
void pushdown(int x,int l,int r,int mid){
	if(tag[x]){
		tag[x<<1]=tag[x<<1|1]=tag[x];
		tree[x<<1]=(mid-l+1)*tag[x];
		tree[x<<1|1]=(r-mid)*tag[x];
		tag[x]=0;
	}
	if(tag2[x]){
		tag2[x<<1]=tag2[x<<1|1]=tag2[x];
		tree2[x<<1]=(mid-l+1)*tag2[x];
		tree2[x<<1|1]=(r-mid)*tag2[x];
		tag2[x]=0;
	}
}
void pradd(int p,int l,int r,int pl,int pr,long long x){
	if(pl<=l&&r<=pr){
		if(x>1e7||x<1){
			tag[p]=0;
		}
		else{
			tag[p]=!a[x];
		}
		tag2[p]=x;
		tree[p]=(r-l+1)*tag[p];
		tree2[p]=(r-l+1)*x;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(p,l,r,mid);
	if(pl<=mid){
		pradd(p<<1,l,mid,pl,pr,x);
	}
	if(mid<pr){
		pradd(p<<1|1,mid+1,r,pl,pr,x);
	}
	psup(p);
} 
pair<int,long long> prsum(int p,int l,int r,int pl,int pr){
	if(pl<=l&&r<=pr){
		return make_pair(tree[p],tree2[p]);
	}
	int mid=(l+r)>>1;
	pushdown(p,l,r,mid);
	pair<int,long long> res;
	res.first=res.second;
	if(pl<=mid){
		res.first+=prsum(p<<1,l,mid,pl,pr).first;
		res.second+=prsum(p<<1,l,mid,pl,pr).second;
	}
	if(mid<pr){
		res.first+=prsum(p<<1|1,mid+1,r,pl,pr).first;
		res.second+=prsum(p<<1|1,mid+1,r,pl,pr).second;
	}
	return res;
}
int main(){
	int q,k,x,l,r;
	char opt;
	cin>>n>>q;
	shai(1e7);
	for(int i=1;i<=n;i++){
		cin>>x;
		sz[i]=x;
	}
	build(1,1,n);
	while(q--){
		cin>>opt;
		if(opt=='A'){
			cin>>k>>x;
			pradd(1,1,n,x,x,prsum(1,1,n,x,x).second+k);
		}
		if(opt=='R'){
			cin>>k>>l>>r;
			pradd(1,1,n,l,r,k);
		}
		if(opt=='Q'){
			cin>>l>>r;
			cout<<prsum(1,1,n,l,r).first<<endl;
		}
	}
	return 0;
}