fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define Lim 10000000
  4. #define MAX 100010
  5. #define lld long long
  6. using namespace std;
  7. bool prime[10000001];
  8. void sieve()
  9. {
  10.     for(int i=2;i*i<=10000000;i++)
  11.     {
  12.         if(prime[i]==0)
  13.         {
  14.         for(int j=i*i;j<=10000000;j+=i)
  15.         prime[j]=1;
  16.         }
  17.     }
  18.     prime[1] = 1;
  19.     prime[0] = 1;
  20. }
  21. bool check(lld n)
  22. {
  23.     if(n>10000000)
  24.     return false;
  25.  
  26.     if(prime[n]==1)
  27.     return false;
  28.  
  29.     else
  30.     return true;
  31.  
  32. }
  33.  
  34. lld tree[4*MAX+1];
  35. lld lazy[4*MAX+1];
  36. lld a[MAX+1];
  37.  
  38. void init(int i,int start,int end)
  39. {
  40.     if(start==end)
  41.     {
  42.         tree[i] = check(a[start]);
  43.         lazy[i]=-1;
  44.         return;
  45.     }
  46.     int mid = (start+end)/2;
  47.     init(2*i,start,mid);
  48.     init(2*i+1,mid+1,end);
  49.     tree[i] = tree[2*i] + tree[2*i+1];
  50.  
  51.     lazy[i]=-1;
  52. }
  53. void refresh(int i,int start,int end)
  54. {
  55.     if(lazy[i]!=-1)
  56.     {
  57.         tree[i] = check(lazy[i]) * (end-start+1);
  58.         if(end>start)
  59.         {
  60.             lazy[2*i] = lazy[i];
  61.             lazy[2*i+1] = lazy[i];
  62.         }
  63.         else
  64.         {
  65.             a[start] = lazy[i];
  66.         }
  67.         lazy[i]=-1;
  68.     }
  69. }
  70. lld query(int i,int start,int end,int qs,int qe)
  71. {
  72.     refresh(i,start,end);
  73.  
  74.     if(qs>end||qe<start)
  75.     return 0;
  76.  
  77.     if(qs<=start&&qe>=end)
  78.     return tree[i];
  79.  
  80.     int mid = (start+end)/2;
  81.  
  82.     return query(2*i,start,mid,qs,qe)+query(2*i+1,mid+1,end,qs,qe);
  83. }
  84.  
  85. void replace(int i,int start,int end,int qs,int qe,lld value)
  86. {
  87.     refresh(i,start,end);
  88.  
  89.     if(qs>end||qe<start)
  90.     return;
  91.  
  92.     if(qs<=start&&qe>=end)
  93.     {
  94.         lazy[i] = value;
  95.         refresh(i,start,end);
  96.         return;
  97.     }
  98.  
  99.     int mid = (start+end)/2;
  100.     replace(2*i,start,mid,qs,qe,value);
  101.     replace(2*i+1,mid+1,end,qs,qe,value);
  102.     tree[i] = tree[2*i]+tree[2*i+1];
  103. }
  104.  
  105. void ADD(int i,int start,int end,int qs,int qe,lld value)
  106. {
  107.    refresh(i,start,end);
  108.  
  109.    if(qs>end||qe<start)
  110.    return;
  111.  
  112.    if(start==end)
  113.    {
  114.        a[start]+=value;
  115.  
  116.        tree[i] = check(a[start]);
  117.        return;
  118.    }
  119.  
  120.    int mid = (start+end)/2;
  121.  
  122.    ADD(2*i,start,mid,qs,qe,value);
  123.    ADD(2*i+1,mid+1,end,qs,qe,value);
  124.  
  125.    tree[i] = tree[2*i] + tree[2*i+1];
  126. }
  127. int swap(int &a,int &b)
  128. {
  129.     a = a+b;
  130.     b = a-b;
  131.     a = a-b;
  132. }
  133. int main()
  134. {
  135.     sieve();
  136.  
  137.     int n,q,start,end;
  138.     lld value;
  139.     char type;
  140.     scanf("%d",&n);
  141.     scanf("%d",&q);
  142.  
  143.     for(int i=0;i<n;i++)
  144.     scanf("%lld",&a[i]);
  145.  
  146.     init(1,0,n-1);
  147.  
  148.     while(q--)
  149.     {
  150.         cin>>type;
  151.  
  152.         if(type=='Q')
  153.            {
  154.                scanf("%d%d",&start,&end);
  155.                if(start>end)
  156.                swap(start,end);
  157.                printf("%lld\n",query(1,0,n-1,start-1,end-1));
  158.            }
  159.  
  160.         else if(type=='A')
  161.         {
  162.             scanf("%lld%d",&value,&start);
  163.             end = start;
  164.             ADD(1,0,n-1,start-1,end-1,value);
  165.         }
  166.         else
  167.         {
  168.             scanf("%lld%d%d",&value,&start,&end);
  169.             if(start>end)
  170.             swap(start,end);
  171.             replace(1,0,n-1,start-1,end-1,value);
  172.         }
  173.     }
  174.  
  175.     return 0;
  176. }
  177.  
  178.  
Success #stdin #stdout 0.17s 20144KB
comments (?)
stdin
copy 
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
stdout
copy 
2
1
2
4
0
4
https://ideone.com/YwZPRr
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!