fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1e6 + 9, MAXX = 1e4 + 9;
  5.  
  6. int n, q, arr[MAXX], tree[MAXX << 2], Lazy[MAXX << 2];
  7. bool Prime[MAX];
  8.  
  9. void Sieve(){
  10.     Prime[0] = Prime[1] = true;
  11.     for(int i=2; i<MAX; i++){
  12.         if(Prime[i]) continue;
  13.         for(long long j=1ll*i*i; j<MAX; j+=i)
  14.             Prime[j] = true;
  15.     }
  16. }
  17.  
  18. void Build(int id = 1, int L = 1, int R = n) {
  19.     if(L == R) {
  20.         tree[id] = !Prime[ arr[L] ];
  21.         return;
  22.     }
  23.     int mid = (L + R) >> 1;
  24.     Build(id << 1, L, mid);
  25.     Build(id << 1 | 1, mid + 1, R);
  26.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  27. }
  28.  
  29. void Propagate(int id, int L, int mid, int R) {
  30.     if(!Lazy[id]) return;
  31.     //if(L == R) return;
  32.     Lazy[id << 1] = Lazy[id];
  33.     Lazy[id << 1 | 1] = Lazy[id];
  34.     tree[id << 1] = !Prime[ Lazy[id] ] * (mid - L + 1);
  35.     tree[id << 1 | 1] = !Prime[ Lazy[id] ] * (R - mid);
  36.     Lazy[id] = 0;
  37. }
  38.  
  39. void Update(int st, int en, int val, int id = 1, int L = 1, int R = n) {
  40.     if(st > R || L > en) return;
  41.     if(st <= L && R <= en) {
  42.         tree[id] = !Prime[val] * (R - L + 1);
  43.         Lazy[id] = val;
  44.         return;
  45.     }
  46.     int mid = (L + R) >> 1;
  47.     Propagate(id, L, mid, R);
  48.     Update(st, en, val, id << 1, L, mid);
  49.     Update(st, en, val, id << 1 | 1, mid + 1, R);
  50.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  51. }
  52.  
  53. int Query(int st, int en, int id = 1, int L = 1, int R = n) {
  54.     if(st <= L && R <= en)
  55.         return tree[id];
  56.     int mid = (L + R) >> 1;
  57.     Propagate(id, L, mid, R);
  58.     if(mid >= en)
  59.         return Query(st, en, id << 1, L, mid);
  60.     if(mid < st)
  61.         return Query(st, en, id << 1 | 1, mid + 1, R);
  62.     return Query(st, en, id << 1, L, mid) + Query(st, en, id << 1 | 1, mid + 1, R);
  63. }
  64.  
  65. int main() {
  66.     int T; scanf("%d", &T);
  67.     Sieve();
  68.     for(int A = 1; A <= T; A++) {
  69.  
  70.         scanf("%d %d", &n, &q);
  71.         for (int i = 1; i <= n; i++)
  72.             scanf("%d", arr + i);
  73.  
  74.         Build();
  75.         printf("Case %d:\n", A);
  76.         while(q--) {
  77.             int t, L, R, val;
  78.             scanf("%d %d %d", &t, &L, &R);
  79.             if(t == 1)
  80.                 printf("%d\n", Query(L, R));
  81.             else {
  82.                 scanf("%d", &val);
  83.                 Update(L, R, val);
  84.             }
  85.         }
  86.     }
  87. }
Success #stdin #stdout 0.01s 4224KB
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/y8V607
language:
C++14 (gcc 8.3)
created:
6 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!