fork download
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int mxN = 1e5 + 5;
  7. vector<int> primes;
  8. int lazy[mxN * 4], a[mxN], n;
  9. bool vis[mxN];
  10.  
  11. struct node {
  12. int val;
  13. int cnt;
  14. } tree[mxN * 4];
  15.  
  16. bool is_prime(int x) {
  17. if(x == 1)
  18. return false;
  19. for(int p : primes)
  20. if(x % p == 0 && x != p)
  21. return false;
  22. return true;
  23. }
  24.  
  25. void propagate(int x, int lx, int rx) {
  26. if(lazy[x] == -1)
  27. return;
  28. tree[x].val = lazy[x];
  29. tree[x].cnt = 0;
  30. if(lazy[x] <= 1e7 && is_prime(lazy[x]))
  31. tree[x].cnt = rx - lx;
  32. if(rx - lx == 1) {
  33. lazy[x] = -1;
  34. return;
  35. }
  36. lazy[2 * x + 1] = lazy[2 * x + 2] = lazy[x];
  37. lazy[x] = -1;
  38. }
  39.  
  40. void build(int x = 0, int lx = 0, int rx = n) {
  41. if(rx - lx == 1) {
  42. tree[x].val = a[lx];
  43. if(a[lx] <= 1e7)
  44. tree[x].cnt = is_prime(a[lx]);
  45. return;
  46. }
  47. int mid = (lx + rx) / 2;
  48. build(2 * x + 1, lx, mid);
  49. build(2 * x + 2, mid, rx);
  50. tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
  51. }
  52.  
  53. void update_point(int node, int v, int x = 0, int lx = 0, int rx = n) {
  54. propagate(x, lx, rx);
  55. if(rx - lx == 1) {
  56. tree[x].val += v;
  57. tree[x].cnt = 0;
  58. if(tree[x].val <= 1e7 && is_prime(tree[x].val))
  59. tree[x].cnt = 1;
  60. return;
  61. }
  62. int mid = (lx + rx) / 2;
  63. if(node < mid)
  64. update_point(node, v, 2 * x + 1, lx, mid);
  65. else
  66. update_point(node, v, 2 * x + 2, mid, rx);
  67. tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
  68. }
  69.  
  70. void range_update(int l, int r, int v, int x = 0, int lx = 0, int rx = n) {
  71. propagate(x, lx, rx);
  72. if(lx >= l && rx <= r) {
  73. lazy[x] = v;
  74. propagate(x, lx, rx);
  75. return;
  76. }
  77. if(lx >= r || l >= rx)
  78. return;
  79. int mid = (lx + rx) / 2;
  80. range_update(l, r, v, 2 * x +1, lx, mid);
  81. range_update(l, r, v, 2 * x +2, mid, rx);
  82. tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
  83. }
  84.  
  85. int query(int l, int r, int x = 0, int lx = 0, int rx = n) {
  86. propagate(x, lx, rx);
  87. if(lx >= l && rx <= r)
  88. return tree[x].cnt;
  89. if(lx >= r || l >= rx)
  90. return 0;
  91. int mid = (lx + rx) / 2;
  92. int c1 = query(l, r, 2 * x + 1, lx, mid);
  93. int c2 = query(l, r, 2 * x +2, mid, rx);
  94. return c1 + c2;
  95. }
  96.  
  97. int main() {
  98. ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  99. int q;
  100. cin >> n >> q;
  101. for(int i = 0; i < n; ++i)
  102. cin >> a[i];
  103. memset(lazy, -1, sizeof lazy);
  104. for(int i = 2; i <= 1e3; ++i) {
  105. if(vis[i])
  106. continue;
  107. primes.push_back(i);
  108. for(int j = i + i; j <= 1e3; j += i)
  109. vis[j] = true;
  110. }
  111. build();
  112. while(q--) {
  113. char c;
  114. cin >> c;
  115. if(c == 'A') {
  116. int v, pos;
  117. cin >> v >> pos;
  118. --pos;
  119. update_point(pos, v);
  120. }
  121. else if(c == 'R') {
  122. int v, l, r;
  123. cin >> v >> l >> r;
  124. --l;
  125. range_update(l, r, v);
  126. }
  127. else {
  128. int l, r;
  129. cin >> l >> r;
  130. --l;
  131. cout << query(l, r) << '\n';
  132. }
  133. }
  134. }
  135.  
Success #stdin #stdout 0s 5104KB
stdin
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
2
1
2
4
0
4