fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5. typedef long long ll;
  6. #define debug(x) cout << #x << " = " << x << '\n'
  7. #define debug_arr(a , n) for(ll i = 0 ; i < n ; i++)cout << a[i] << " "
  8. #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  9. #define mp make_pair
  10. #define pb push_back
  11. #define ff first
  12. #define ss second
  13. #define vi vector<ll>
  14. #define vll vector<ll> 
  15. #define inf 1000000000
  16. #define mod 1000000007
  17.  
  18. const ll max_n = 1e5 + 9;
  19. const ll Max_n = 1e6 + 9;
  20.  
  21. typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
  22. ll power(ll a , ll b)
  23. {
  24.     ll prod = 1;
  25.     while(b)
  26.     {
  27.         if(b&1)
  28.         prod = (prod*a)%mod;
  29.         a = (a*a)%mod;
  30.         b >>= 1;
  31.     }
  32.     return prod;
  33. }
  34.  
  35. ll t[4*max_n];
  36. ll lazy[4*max_n];
  37.  
  38. ll a[max_n];
  39. ll isprime[Max_n];
  40. void init(){
  41.     isprime[0] = isprime[1] = 1;
  42.     for(ll i = 2 ; i*i < Max_n ; i++){
  43.         if(isprime[i] == 0){
  44.             for(ll j = i*i ; j < Max_n ; j += i){
  45.                 isprime[j] = 1;
  46.             }
  47.         }
  48.     }
  49. }
  50. void build(ll v , ll l , ll r){
  51.     if(l == r){
  52.         t[v] = isprime[a[l]] ^ 1;
  53.     }
  54.     else
  55.     {
  56.         ll tm = (l + r) >> 1;
  57.         build(2*v , l , tm);
  58.         build(2*v + 1 , tm+1 , r);
  59.         t[v] = t[2*v] + t[2*v+1];
  60.     }
  61. }
  62. void update(ll v,  ll tl , ll tr , ll l , ll r , ll ele){
  63.     if(lazy[v]){
  64.         t[v] = (tr - tl + 1) * (isprime[lazy[v]] ^ 1);
  65.         if(l != r){
  66.             lazy[2*v] = lazy[v];
  67.             lazy[2*v+1] = lazy[v];
  68.         }
  69.         lazy[v] = 0;
  70.     }
  71.     if(l > r){
  72.         return;
  73.     }
  74.     if(l == tl && r == tr){
  75.         t[v] = (isprime[ele] ^ 1) * (r - l + 1);
  76.         if(l != r){
  77.             lazy[2*v] = ele;
  78.             lazy[2*v+1] = ele;
  79.         }
  80.     }
  81.     else
  82.     {
  83.         ll tm = (tl + tr) >> 1;
  84.         update(2*v , tl , tm , l , min(r , tm) , ele);
  85.         update(2*v+1 , tm+1 , tr , max(l , tm+1) , r , ele);
  86.         t[v] = t[2*v] + t[2*v+1];
  87.     }
  88. }
  89. ll query(ll v , ll tl , ll tr , ll l , ll r){
  90.     if(lazy[v]){
  91.         t[v] = (tr - tl + 1)*(isprime[lazy[v]]^1);
  92.         if(tl != tr){
  93. 			lazy[2*v] = lazy[v];
  94.             lazy[2*v+1] = lazy[v];
  95.         }
  96.         lazy[v] = 0;
  97.     }
  98.     if(l > r)return 0;
  99.     if(l == tl && r == tr){
  100.         return t[v];
  101.     }
  102.     ll tm = (tl + tr) >> 1;
  103.     return query(2*v , tl , tm , l , min(r , tm)) + query(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
  104. }
  105. int main()
  106. {
  107.     int T;
  108.     cin >> T;
  109.     init();
  110.  
  111.  
  112.     for(int x = 1 ; x <= T ; x++){
  113.         cout << "Case " << x << ":" << endl;
  114.         ll n , q;
  115.         cin >> n >> q;
  116.         memset(a , 0 , sizeof(a));
  117.         memset(t , 0 , sizeof(t));
  118.         memset(lazy , 0 , sizeof(lazy));
  119.         for(ll i = 0 ; i < n ; i++){
  120.             cin >> a[i];
  121.         }
  122.         build(1 , 0 , n-1);
  123.         // cout << t[1] << endl;
  124.         while(q--){
  125.             ll op;
  126.             cin >> op;
  127.             if(op == 1){
  128.                 ll l , r;
  129.                 cin >> l >> r;
  130.                 l-- , r--;
  131.                 cout << query(1 , 0 , n-1 , l , r) << endl;
  132.             }
  133.             else{
  134.                 ll l , r , ele;
  135.                 cin >> l >> r >> ele;
  136.                 l-- , r--;
  137.                 update(1 , 0 , n-1 , l , r , ele);
  138.             }
  139.         }
  140.     }
  141.     return 0;
  142. }
  143.  
Success #stdin #stdout 0.01s 18404KB
comments (?)
stdin
copy 
1

5 3

78 2 13 12 3

1 1 2

0 4 4 5

1 1 5
stdout
copy 
Case 1:
1
4
https://ideone.com/Hiy4EJ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!