Prime Query

Time Limit: 1 Second Memory Limit: 196608 KB

You are given a simple task. Given a sequence A[i] with N numbers. You have to perform Q operations on the given sequence.

Here are the operations:

A v l, add the value v to element with index l.(1<=V<=1000)

R a l r, replace all the elements of sequence with index i(l<=i<= r) with a(1<=a<=10^6) .

Q l r, print the number of elements with index i(l<=i<=r) and A[i] is a prime number

Note that no number in sequence ever will exceed 10^7.

Input

The first line is a signer integer T which is the number of test cases.

For each test case, The first line contains two numbers N and Q (1 <= N, Q <= 100000) - the number of elements in sequence and the number of queries.

The second line contains N numbers - the elements of the sequence.

In next Q lines, each line contains an operation to be performed on the sequence.

Output

For each test case and each query,print the answer in one line.

Sample Input

1

5 10

1 2 3 4 5

A 3 1

Q 1 3

R 5 2 4

A 1 1

Q 1 1

Q 1 2

Q 1 4

A 3 5

Q 5 5

Q 1 5

Sample Output

2

1

2

4

0

4

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <set>

#include <map>

#include <vector>

#include <cmath>

#define VI vector<int>

#define VP vector<Point>

#define pr pair<int,int>

#define LL long long

#define fread() freopen("../in.in","r",stdin)

#define fwrite() freopen("out.out","w",stdout)

using namespace std;

const int Max = 1e7;

const int Maxn = 100000;

typedef struct Tree

{

    int num;//记录所在区间的素数的个数

    int lazy;//标记所在的区间有没有被整体更新

} Tree;

int vis[Max+1000];

Tree Tr[Maxn*5];

int a[Maxn+100];

void init()//素数表

{

    memset(vis,0,sizeof(vis));

    int  m= (int)sqrt(Max);

    vis[0]=1;

    vis[1]=1;

    for(LL i=2; i<=m; i++)

    {

        if(!vis[i])

        {

            for(LL j=i*i; j<=Max; j+=i)

            {

                vis[j]=1;

            }

        }

    }

}

void Pushup(int st,int L,int R)//线段树区间向上更新

{

    if(Tr[st<<1|1].lazy&&Tr[st<<1].lazy&&Tr[st<<1|1].lazy==Tr[st<<1].lazy)//

    {

        Tr[st].lazy=Tr[st<<1].lazy;

    }

    else

    {

        Tr[st].lazy=0;

    }

    Tr[st].num=Tr[st<<1].num+Tr[st<<1|1].num;

}

void Pushdown(int st,int L,int R)//线段树区间向下更新

{

    if(Tr[st].lazy&&L!=R)

    {

        int mid =(L+R)>>1;

        Tr[st<<1].lazy=Tr[st<<1|1].lazy=Tr[st].lazy;

        if(Tr[st].num)

        {

            Tr[st<<1|1].num=R-mid;

            Tr[st<<1].num=mid+1-L;

        }

        else

        {

            Tr[st<<1|1].num=Tr[st<<1].num=0;

        }

        Tr[st].lazy=0;

    }

}

void Build(int L,int R,int st)//初始化线段树

{

    Tr[st].lazy=0;

    Tr[st].num=0;

    if(L==R)

    {

        Tr[st].lazy=a[L];

        Tr[st].num=(!vis[a[L]]);

        return ;

    }

    int mid=(L+R)>>1;

    Build(L,mid,st<<1);

    Build(mid+1,R,st<<1|1);

    Pushup(st,L,R);

}

void Add(int L,int R,int st,int s,int d)//单点更新

{

    Pushdown(st,L,R);

    if(L==s&&R==s)

    {

        Tr[st].lazy+=d;

        Tr[st].num=(!vis[Tr[st].lazy]);

        return ;

    }

    int mid =(L+R)>>1;

    if(s<=mid)

    {

        Add(L,mid,st<<1,s,d);

    }

    else

    {

        Add(mid+1,R,st<<1|1,s,d);

    }

    Pushup(st,L,R);

}

void Update(int L,int R,int st,int l,int r,int d)//区间更新

{

    if(L>r||R<l)

    {

        return ;

    }

    if(L>=l&&R<=r)

    {

        Tr[st].lazy=d;

        Tr[st].num=(!vis[d])*(R-L+1);

        return ;

    }

    Pushdown(st,L,R);

    int mid = (L+R)>>1;

    if(l<=mid)

    {

        Update(L,mid,st<<1,l,r,d);

    }

    if(r>mid)

    {

        Update(mid+1,R,st<<1|1,l,r,d);

    }

    Pushup(st,L,R);

}

int Query(int L,int R,int st,int l,int r)//区间查询

{

    if(L>r||R<l)

    {

        return 0;

    }

    Pushdown(st,L,R);

    if(L>=l&&R<=r)

    {

        return Tr[st].num;

    }

    int mid=(L+R)>>1;

    int sum=0;

    if(l<=mid)

    {

        sum+=Query(L,mid,st<<1,l,r);

    }

    if(r>mid)

    {

        sum+=Query(mid+1,R,st<<1|1,l,r);

    }

    Pushup(st,L,R);

    return sum;

}

int main()

{

    int T,n,q;

    int l,r,s,d;

    char op[3];

    init();

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d %d",&n,&q);

        for(int i=1; i<=n; i++)

        {

            scanf("%d",&a[i]);

        }

        Build(1,n,1);

        while(q--)

        {

            scanf("%s",op);

            if(op[0]=='A')

            {

                scanf("%d %d",&d,&s);

                Add(1,n,1,s,d);

            }

            else if(op[0]=='Q')

            {

                scanf("%d %d",&l,&r);

                printf("%d\n",Query(1,n,1,l,r));

            }

            else if(op[0]=='R')

            {

                scanf("%d %d %d",&d,&l,&r);

                Update(1,n,1,l,r,d);

            }

        }

    }

    return 0;

}