zoj3911 线段树区间修改与求素数的结合

迷南。 2022-08-09 14:51 83阅读 0赞

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

**题意：给定n个数，两种操作，修改和添加。每次询问l到r之间的素数的个数。**

**分析：由于输入的数据有空格，所以慎用getchar（）。。用scanf("%s")，就行啦。线段树还不够熟悉，足足写了一个多小时。。**

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=10000100;
    
    bitset<N> vis;
    
    struct st
    {
        int l,r,flag,num,val;
    }a[400040];
    
    inline void PushUp(int i)
    {
        a[i].num=a[i<<1].num+a[i<<1|1].num;
    }
    
    inline void PushDown(int i)
    {
        if(a[i].flag)
        {
            a[i<<1].flag=a[i<<1|1].flag=1;
            a[i<<1].val=a[i<<1|1].val=a[i].val;
            int t=a[i].val;
            bool f;
            if(t%2==0 && t!=2)f=0;
            else if(!vis[t]) f=1;
            else f=0;
            if(f)
            {
                a[i<<1].num=a[i<<1].r-a[i<<1].l+1;
                a[i<<1|1].num=a[i<<1|1].r-a[i<<1|1].l+1;
            }
            else
            {
                a[i<<1].num=a[i<<1|1].num=0;
            }
            a[i].flag=0;
        }
    }
    void build(int l,int r,int i)
    {
        a[i].l=l;
        a[i].r=r;
        a[i].flag=0;
        if(l==r)
        {
            a[i].val=in();
            if(a[i].val%2==0 && a[i].val!=2) a[i].num=0;
            else{
                if(!vis[a[i].val]) a[i].num=1;
                else a[i].num=0;
            }
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        PushUp(i);
    }
    void update(int l,int r,int val,int i,char c)
    {
        if(a[i].l>=l && a[i].r<=r)
        {
            a[i].flag=1;
    
            if(c=='a') a[i].val += val;
            else a[i].val=val;
    
            bool f;
            if(a[i].val%2==0 && a[i].val!=2) f=0;
            else if(!vis[a[i].val]) f=1;
            else f=0;
            if(f) a[i].num=a[i].r-a[i].l+1;
            else a[i].num=0;
            return;
        }
        PushDown(i);
        int mid=(a[i].l+a[i].r)>>1;
        if(l>mid)
        {
            update(l,r,val,i<<1|1,c);
        }
        else if(r<=mid)
        {
            update(l,r,val,i<<1,c);
        }
        else
        {
            update(l,mid,val,i<<1,c);
            update(mid+1,r,val,i<<1|1,c);
        }
        PushUp(i);
    }
    int query(int l,int r,int i)
    {
        if(a[i].l>=l && a[i].r<=r) return a[i].num;
        if(a[i].l>r || a[i].r<l) return 0;
        PushDown(i);
        return query(l,r,i<<1)+query(l,r,i<<1|1);
    }
    int main()
    {
        vis[0]=vis[1]=1;
        for(int i=3;i*i<N;i+=2)
        {
            if(!vis[i]) for(int j=i*i;j<N;j+=i<<1) vis[j]=1;
        }
    
        int T=in();
        while(T--)
        {
            int n=in(),q=in();
            build(1,n,1);
            char cmd[3];
            while(q--)
            {
                scanf("%s",cmd);
                if(cmd[0]=='A')
                {
                    int val=in(),pos=in();
                    update(pos,pos,val,1,'a');
                }
                else if(cmd[0]=='R')
                {
                    int val=in(),l=in(),r=in();
                    update(l,r,val,1,'r');
                }
                else
                {
                    int l=in(),r=in();
                    printf("%d\n",query(l,r,1));
    
                }
            }
        }
        return 0;
    }