fork download 
  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define maxn 100007
  5. #define ll long long 
  6. #define br '\n'
  7. #define pb push_back
  8. #define mod1 1000000007
  9. #define mod 998244353
  10. #define INF  0x3f3f3f3f
  11. #define limit 1e18
  12.  
  13.  
  14.  
  15.  
  16. set<ll>um;
  17.  
  18. void seive()
  19. {
  20. 	ll n=1e6 + 1;
  21.  
  22. 	bool prime[n+1];
  23. 	memset(prime,true,sizeof(prime));
  24.  
  25. 	for(ll p=2;p*p<=n;p++)
  26. 	{
  27. 		if(prime[p]==true)
  28. 		{
  29. 			for(ll i=p*p;i<=n;i+=p)
  30. 			{
  31. 				prime[i]=false;
  32. 			}
  33. 		}
  34. 	}
  35. 	for (int p = 2; p <= n; p++)
  36. 	{
  37.         if (prime[p])
  38.         {
  39.         	um.insert(p);
  40.         }
  41.     }
  42. }
  43.  
  44.  
  45.  
  46.  
  47.  
  48. typedef struct Node
  49. {
  50.  
  51.  
  52.     ll data=0;
  53.  
  54. }Node;
  55.  
  56.  
  57.  
  58.  
  59. Node seg[4*100001];
  60. Node lazy[4*100001];
  61. vector<ll>arr;
  62.  
  63. void setup()
  64. {
  65. 	for(ll i=0;i<4*100001;i++)
  66. 	{
  67. 		seg[i].data=0;
  68. 		lazy[i].data=0;
  69. 	}
  70. }
  71.  
  72.  
  73. Node merge(Node leftChild, Node rightChild)
  74. {
  75.     Node parentNode;
  76.  
  77.     parentNode.data=leftChild.data+rightChild.data;
  78.  
  79.     return parentNode;
  80.  
  81.  
  82. }
  83.  
  84.  
  85.  
  86. void build(ll index,ll low,ll high)
  87. {
  88.     if(low==high)
  89.     {
  90.  
  91.         seg[index].data=arr[low];
  92.         return;
  93.     }
  94.     ll mid=(low+high)/2;
  95.     build(2*index+1,low,mid);
  96.     build(2*index+2,mid+1,high);
  97.     seg[index]=merge(seg[2*index+1],seg[2*index+2]);
  98. }
  99.  
  100.  
  101.  
  102.  
  103. void update(ll index,ll low,ll high,ll l,ll r,ll val)
  104. {
  105.     if(lazy[index].data!=0)
  106.     {
  107.         seg[index].data +=(high-low+1)*(lazy[index].data);
  108.         if(low!=high)
  109.         {
  110.             lazy[2*index+1].data +=lazy[index].data;
  111. 			lazy[2*index+2].data +=lazy[index].data;
  112.         }
  113.         lazy[index].data=0;
  114.     }
  115.  
  116.     if(r<low || l>high || low>high)
  117.     {
  118.         return;
  119.     }
  120.  
  121.     if(low>=l && high<=r)
  122.     {
  123.  
  124.         seg[index].data =(high-low+1)*val;
  125.  
  126.         if(low!=high)
  127.         {
  128.  
  129.  
  130.             lazy[2*index+1].data+=val;
  131.             lazy[2*index+2].data+=val;
  132.  
  133.  
  134.         }
  135.         return ;
  136.     }
  137.  
  138.     ll mid=(high+low)/2;
  139.     update(2*index+1,low,mid,l,r,val);
  140.     update(2*index+2,mid+1,high,l,r,val);
  141.     seg[index]=merge(seg[2*index+1],seg[2*index+2]);
  142. }
  143.  
  144.  
  145. ll  query(ll index,ll low,ll high,ll l,ll r)
  146. {
  147. 	if(lazy[index].data!=0)
  148. 	{
  149. 		seg[index].data +=(high-low+1)* (lazy[index].data);
  150. 		if(low!=high)
  151. 		{
  152. 			lazy[2*index+1].data +=lazy[index].data;
  153. 			lazy[2*index+2].data +=lazy[index].data;
  154. 		}
  155. 		lazy[index].data=0;
  156. 	}
  157.  
  158.  
  159.  
  160. 	if(r<low || l>high || low>high)
  161. 	{
  162. 		return 0;
  163. 	}
  164.  
  165. 	if(low>=l && high<=r)
  166. 	{
  167. 		return seg[index].data;
  168. 	}
  169.  
  170. 	ll mid=(low+high)/2;
  171. 	return query(2*index+1,low,mid,l,r)+query(2*index+2,mid+1,high,l,r);
  172.  
  173. }
  174.  
  175. void solve()
  176. {
  177.     ll n,q,type,x,y,val;
  178.  
  179.      scanf("%lld %lld",&n,&q);
  180.  
  181.  	setup();
  182.     arr.resize(n);
  183.     for(ll i=0;i<n;i++)
  184.     {
  185.  
  186.         scanf("%lld",&arr[i]);
  187.         ll v=0;
  188.         if(um.find(arr[i])!=um.end())
  189.        	{
  190.        		v=1;
  191.        	}
  192.        	arr[i]=v;
  193.  
  194.  
  195.     }
  196.     build(0,0,n-1);
  197.     ll l;
  198.  
  199.  
  200.     for(ll i=0;i<q;i++)
  201.     {
  202.         cin>>type;
  203.         if(type==1)
  204.         {
  205.  
  206.             cin>>x>>y;
  207.  
  208.             x--;
  209.             y--;
  210.             ll ans=query(0,0,n-1,x,y);
  211.  
  212.  
  213.  
  214.             printf("%lld\n", ans);
  215.         }
  216.         else
  217.         {
  218.             cin>>x>>y>>val;
  219.            	x--;
  220.            	y--;
  221.            	ll v=0;
  222.            	if(um.find(val)!=um.end())
  223.            	{
  224.            		v=1;
  225.            	}
  226.             update(0,0,n-1,x,y,v);
  227.         }
  228.     }
  229.  
  230. }
  231.  
  232. int main()
  233. {
  234.  
  235.     int t=1;
  236.     seive();
  237.     cin>>t;
  238.     for(ll t1=1;t1<=t;t1++)
  239.     {
  240.  
  241.     	printf("Case %lld:\n", t1);
  242.         solve();
  243.     }
  244. }
  245.  
  246.  
Success #stdin #stdout 0.02s 14772KB
comments (?)
stdin 
1
5 3
78 2 13 12 3
1 1 2
0 4 4 5
1 1 5
stdout 
Case 1:
1
4
https://ideone.com/ybMN8P
language:
C++14 (gcc 8.3)
created:
4 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!