D题题解_牛客博客

题意：

根据题目操作进行模拟，问区间有多少个质数。

题解：

说到质数，都知道质数是一个只有1和它本身的数，那么在题目操作下，什么时候可以出现质数呢？有两种情况可以出现质数。

情况一： $x = 1$ 时，当且仅当 $a_{i} = 1, 且 i 是质数$ ；

情况二： $x = 0$ 时，当且仅当 $a_{i} 是质数$ ;

需要注意的是，有一个特殊的地方——下标1，这个地方如果是质数的话，无论x是多少这个数依旧是质数，因为 $1^{x} = 1$ ，1乘一个质数还是质数，所以这个位置需要特判。

其实这题差不多是一道模板题，势能线段树的模板题，所以不会的同学，可以去看看这个模板，看完你们就知道怎么写这道题了。 ~~(小声哔哔：这题确实挺绝望的，调代码真的很绝望，代码太长了！！！）~~

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
typedef long long ll;
int a[N],n,m;
struct node{
	int L,R;
	int add,sum,lz;
	//add是一段区间中数组是1并且下标是质数的个数；
	//sum是一段区间中质数的个数；
	//lz是一段区间需要乘的次数的懒标记； 
}tree[4*N];

inline int read()
{
	int x=0,p=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') p=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*p;
}

int vis[N],prime[N],tot=0;
inline void pre()//预处理，vis是标记不是质数的数组，prime是质数数组，tot是有多少个质数； 
{
	vis[0]=vis[1]=1;
	for(int i=2;i<=500010;i++)
	{
		if(!vis[i])
			prime[++tot]=i;
		for(int j=1;j<=tot&&(ll)prime[j]*i<=500010;j++)
		{
			vis[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}

inline void push_up(int node)//子节点重新更新父节点的内容； 
{
	tree[node].add=tree[node<<1].add+tree[node<<1|1].add;
	tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
}

inline void build(int node,int L,int R)//一个常规的建树操作； 
{
	tree[node].L=L,tree[node].R=R;
	tree[node].lz=0;
	if(L==R)
	{
		tree[node].sum=vis[a[L]]^1;
		if(a[L]==1&&vis[L]==0)
			tree[node].add=1;
		else tree[node].add=0;
		return ;
	}
	
	int mid=(L+R)>>1;
	int L_node=node<<1,R_node=node<<1|1;
	build(L_node,L,mid);
	build(R_node,mid+1,R);
	push_up(node);
}

inline void push_down(int node)//更新子节点的内容； 
{
	if(tree[node].lz>0)
	{
		tree[node<<1].lz=min(2,tree[node<<1].lz+tree[node].lz);
		tree[node<<1|1].lz=min(2,tree[node<<1|1].lz+tree[node].lz);
		for(int i=1;i<=tree[node].lz;i++)
		{
			tree[node<<1].sum=tree[node<<1].add;
			tree[node<<1].add=0;
			tree[node<<1|1].sum=tree[node<<1|1].add;
			tree[node<<1|1].add=0;
		}
		tree[node].lz=0;
	}
}

inline void modify(int node,int L,int R,int k)//修改操作； 
{ 
	if(L<=tree[node].L&&tree[node].R<=R)
	{
		tree[node].lz=min(2,k+tree[node].lz);
		for(int i=1;i<=tree[node].lz;i++)
		{
			tree[node].sum=tree[node].add;
			tree[node].add=0;
		}
		return ;
	}
	push_down(node);
	
	int mid=(tree[node].L+tree[node].R)>>1;
	if(L<=mid)
		modify(node<<1,L,R,k);
	if(R>mid)
		modify(node<<1|1,L,R,k);
	push_up(node);
}

inline int query(int node,int L,int R)
{ 
	if(tree[node].L>=L&&tree[node].R<=R)
		return tree[node].sum;
	push_down(node);//父节点的内容传下去！！！
	
	int mid=(tree[node].L+tree[node].R)>>1;
	int ans=0;
	if(L<=mid)
		ans+=query(node<<1,L,R);
	if(R>mid)
		ans+=query(node<<1|1,L,R);
	return ans;
}

int main()
{
	pre();
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,1,n);
	
	while(m--)
	{
		int l,r,op;
		op=read(),l=read(),r=read();
		if(op==1)
		{
			int x;
			x=read();
			if(x>=1)
			{
				if(l==1&&l+1<=r)
					modify(l,l+1,r,x);
				else
					modify(1,l,r,x);
			}
		}
		printf("%d\n",query(1,l,r));
	}
	return 0;
}