题意

给定一段序列,有两种操作,第一种是对区间 [l,r][l,r][l,r] 内的每个数乘上 ixi^xixiii 为元素位置,然后输出区间 [l,r][l,r][l,r] 内的素数个数,第二种直接输出区间 [l,r][l,r][l,r] 内素数个数。

分析

1.对于一个合数,无论接下来乘上任何数都不会是素数,也就是对答案无贡献。
2.对于一个素数,如果乘上一个大于 111 的数后,其将不再为素数,不再对答案有贡献。
3.对于 111 这个数就有点不一样了,它本身不属于质数,但若是乘上一个质数后,它就变为素数,对答案贡献加一。但仅有一次机会对答案有贡献,如果变为素数后,同第 222 点。
4.对于第一位置,因为乘上的永远都是 111,所以特殊处理是否为素数即可。

题解

讨论完所有的情况,可以发现一个数最多乘上 222 次后就不再为素数(乘上一次可能变为素数)。
因此我们考虑势能线段树维护序列(说白了就是暴力修改,直到该区间被打上标记说不需要进去修改。)
对线段树每个节点维护一个 tagtagtag 值,代表乘上了多少次 iiiiii 为元素位置。
1.1.对于合数打上标记即可;1.

2.2.对于素数,打上标记并把答案减一;2.

3.113.对于1,特殊考虑乘上的是几次方,如果是1次方且该位置下标为素数,则答案加一,否则答案不变。3.11

4.4.以上所有情况都不涉及下标为 4.1 的元素,将其拉出来特殊处理。

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn=2e5+5;

int a[maxn],pri[maxn*3],vis[maxn*3],cnt,n,m,b,op,u,v,w;
struct node{
    int l,r,w,tag;
}t[maxn<<2];

inline void getpri()
{
    vis[0]=vis[1]=1;
    for(int i=2;i<=5e5;i++)
    {
        if(!vis[i])pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=5e5;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
    return;
}

void pushup(int k)
{
    t[k].w=t[k<<1].w+t[k<<1|1].w;
}

void pushdown(int k)
{
    if(t[k].tag>=2)
    {
        t[k<<1].w=t[k<<1|1].w=0;
        t[k<<1].tag=t[k<<1|1].tag=t[k].tag;
    }
    return;
}

void build(int k,int l,int r)
{
    t[k].l=l,t[k].r=r;
    if(l==r){t[k].w=!vis[a[l]]; if(l==1)t[k].tag=2;return;}
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k); return;
}

void update(int k,int l,int r,int up)
{
    int x=t[k].l,y=t[k].r;
    if(l<=x&&y<=r&&t[k].tag+up>=2){t[k].w=0; t[k].tag+=up; return;}
    if(x==y)
    {
    	if(x==1)return;
    	if(t[k].tag+up>=2)t[k].w=0,t[k].tag+=up;
    	else if(a[x]==1&&!vis[x])t[k].tag+=up,t[k].w=1;
    	else t[k].w=0,t[k].tag+=up;
    	return;
	}
	int mid=x+y>>1; pushdown(k);
    if(l<=mid&&t[k<<1].tag<2)update(k<<1,l,r,up);
    if(mid<r&&t[k<<1|1].tag<2)update(k<<1|1,l,r,up);
    pushup(k); return;
}

int query(int k,int l,int r)
{
    int x=t[k].l,y=t[k].r;
    if(l<=x&&y<=r)return t[k].w;
    int mid=x+y>>1,res=0; pushdown(k);
    if(l<=mid)res+=query(k<<1,l,r);
    if(mid<r)res+=query(k<<1|1,l,r);
    return res;
}

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
    cin>>n>>m>>b; getpri(); b=!vis[b];
    for(int i=2;i<=n;i++)cin>>a[i];
    build(1,1,n); 
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>u>>v>>w;
            int ans=u==1?b:0;
            if(v>1&&w)update(1,u,v,w);
            if(v>1)ans+=query(1,u,v);
            cout<<ans<<"\n";
        }
        else
        {
            cin>>u>>v;
            int ans=u==1?b:0;
            if(v>1)ans+=query(1,u,v);
            cout<<ans<<"\n";
        }
    }
    return 0;
}