fork download
  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
stdin
1

5 3

78 2 13 12 3

1 1 2

0 4 4 5

1 1 5
stdout
Case 1:
1
4