C++(g++ 7.5.0) 解法, 执行用时: 417ms, 内存消耗: 19604K, 提交时间: 2023-01-19 18:44:24

#include <bits/stdc++.h>
#define int long long
using namespace std;
int fa1[500005],fap[500005],a[500005];
int tree[500005];
bitset <500005> p;
inline int lowbit(int x) {
	return x&-x;
}
inline int ask(int x) {
	if(!x) return 0;
	return tree[x]+ask(x^lowbit(x));
}
inline void add(int x,int y) {
	if(x>500000) return ;
	tree[x]+=y,add(x+lowbit(x),y);
}
inline int ff1(int x) {
	if(fa1[x]==x) return x;
	return fa1[x]=ff1(fa1[x]);
}
inline int ffp(int x) {
	if(fap[x]==x) return x;
	return fap[x]=ffp(fap[x]);
}
set <int> s;
inline void change(int l,int r,int x) {
	if(!x) return ;
	l=max(l,2ll);
	while(1)
	{
		int x=*s.lower_bound(l);
		if(x>r) break;
		add(x,-1),s.erase(x); 
	}
	for(int i=ff1(l);i<=r;i=ff1(i+1))
	{
	//	cout << i << "\n";
		if(!p[i]&&x==1) {
			add(i,1),s.insert(i);
		}
		fa1[i]=ff1(i+1);
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	s.insert(100000000);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		fa1[i]=fap[i]=i;
	}
	p[1]=1;
	for(int i=2;i<=500000;i++) {
		if(!p[i]) {
			for(int j=i+i;j<=500000;j+=i) {
				p[j]=1;
			}
		}
	}
	fap[n+1]=fa1[n+1]=n+1;
	for(int i=1;i<=n;i++) {
		if(p[a[i]]) {
			fap[i]=ffp(i+1);
		}
		else {
			add(i,1),s.insert(i);
		}
		if(a[i]!=1) {
			fa1[i]=ff1(i+1);
		}
	}
	while(m--) {
		int op,l,r,x;
		cin >> op >> l >> r;
		if(op==1) {
			cin >> x;
			change(l,r,x);
		}
		cout << ask(r)-ask(l-1) << "\n"; 
	}
	return 0;
}
/*
5 4
1 1 1 1 1
2 1 5
1 1 5 1
1 3 4 2
2 1 5
*/

C++ 解法, 执行用时: 143ms, 内存消耗: 24708K, 提交时间: 2021-10-22 20:06:16

#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int read(){
	char c;int x=0;
	do c=getchar();while(!isdigit(c));
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	return x;
}
int n,m,p[M],zhi[M];
struct seg{
	int l,r,s,h;
	seg*ls,*rs;
	void push_up(){
		s=ls->s+rs->s;
		h=ls->h&&rs->h;
	}
	void build(int u,int v){
		l=u;r=v;
		if(r-l==1){
			s=read();
			if(p[s])h=1;
			if(s==1||p[s])s=0;
			else s=1;
			return;
		}
		ls=new seg{};
		rs=new seg{};
		ls->build(l,l+r>>1);
		rs->build(l+r>>1,r);
		push_up();
	}
	void add(int u,int v,int x){
		if(h)return;
		if(l>=v||r<=u)return;
		if(r-l==1){
			if(l==1)return;
			if(!s&&!h&&x==1&&!p[l])s=1;
			else s=0,h=1;
			return;
		}
		ls->add(u,v,x);
		rs->add(u,v,x);
		push_up();
	}
	int ask(int u,int v){
		if(!s)return 0;
		if(l>=v||r<=u)return 0;
		if(l>=u&&r<=v)return s;
		return ls->ask(u,v)+rs->ask(u,v);
	}
}S;
int main(){
	int t=0,x,y,z;
	for(int i=2;i<M;i++){
		if(!p[i])zhi[t++]=i;
		for(int j=0;zhi[j]*i<M;j++){
			p[i*zhi[j]]=1;
			if(i%zhi[j]==0)break;
		}
	}
	n=read();
	m=read();
	S.build(1,n+1);
	while(m--){
		t=read();
		x=read();
		y=read();
		if(t==1){
			z=read();
			if(z)S.add(x,y+1,z);
		}
		cout<<S.ask(x,y+1)<<'\n';
	}
	return 0;
}