fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
2
1
2
4
0
4
https://ideone.com/me023F
language:
C++ (gcc 8.3)
created:
3 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!