ZOJ 3911 Prime Query

Prime Query

Time Limit: 1 Second      

Memory Limit: 196608 KB

You are given a simple task. Given a sequence A[i] with N

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]

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

Input

The first line is a signer integer T

For each test case, The first line contains two numbers N and Q (1 <= N, Q

The second line contains N

In next Q

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

4

預處理一下一千萬的素數，然後線段樹搞定

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000005;
int T,n,m,p[maxn],u[maxn/10],tot=0;
int l,r,x;
char ch[2];

void pre()
{
  p[0]=p[1]=1;
  for (int i=2;i<maxn;i++)
  {
    if (p[i]==0) u[tot++]=i;
    for (int j=0;j<tot&&i*u[j]<maxn;j++)
    {
      p[i*u[j]]=1;
      if (i%u[j]==0) break;
    }
  }
}

struct ST
{
  const static int maxn=500005;
  int f[maxn],u[maxn];
  void update(int x)
  {
    u[x]=u[x+x]+u[x+x+1];
    f[x]=0;
  }
  void build(int x,int l,int r)
  {
    if (l==r) 
    {
      scanf("%d",&f[x]);
      u[x]=p[f[x]]^1;
    }
    else 
    {
      int mid=l+r>>1;
      build(x+x,l,mid);
      build(x+x+1,mid+1,r);
      update(x);
    }
  }
  void down(int x,int l,int r)
  {
    int mid=l+r>>1;
    f[x+x]=f[x+x+1]=f[x]; f[x]=0;
    u[x+x]=(p[f[x+x]]^1)*(mid-l+1);
    u[x+x+1]=(p[f[x+x+1]]^1)*(r-mid);
  }
  void add(int x,int l,int r,int a,int b)
  {
    if (l==r) {f[x]+=b; u[x]=p[f[x]]^1;}
    else
    {
      if (f[x]) down(x,l,r);
      int mid=l+r>>1;
      if (a<=mid) add(x+x,l,mid,a,b);
      else add(x+x+1,mid+1,r,a,b);
      update(x);
    }
  }
  void change(int x,int l,int r,int ll,int rr,int b)
  {
    if (ll<=l&&r<=rr) {f[x]=b; u[x]=(p[b]^1)*(r-l+1);}
    else 
    {
      int mid=l+r>>1;
      if (f[x]) down(x,l,r);
      if (ll<=mid) change(x+x,l,mid,ll,rr,b);
      if (rr>mid) change(x+x+1,mid+1,r,ll,rr,b);
      update(x);
    }
  }
  int query(int x,int l,int r,int ll,int rr)
  {
    int ans=0;
    if (ll<=l&&r<=rr) ans=u[x];
    else 
    {
      int mid=l+r>>1;
      if (f[x]) down(x,l,r);
      if (ll<=mid) ans+=query(x+x,l,mid,ll,rr);
      if (rr>mid) ans+=query(x+x+1,mid+1,r,ll,rr);
    }
    return ans;
  }
}st;

int main()
{
  pre();
  scanf("%d",&T);
  while (T--)
  {
    scanf("%d%d",&n,&m);
    st.build(1,1,n);
    while (m--)
    {
      scanf("%s",ch);
      switch (ch[0])
      {
        case 'A':scanf("%d%d",&x,&l);
        st.add(1,1,n,l,x); break;
        case 'Q':scanf("%d%d",&l,&r);
          printf("%d\n",st.query(1,1,n,l,r));break;
        case 'R':scanf("%d%d%d",&x,&l,&r);
          st.change(1,1,n,l,r,x); break;
      }
    }
  }
  return 0;
}