fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 3e5 + 5;  
  11. const int MAX_A = 1e6 + 5;  
  12.  
  13. // Nhận xét quan trọng: D(a(i)) ~ cbrt(a(i)), đối với a(i) <= 1e6 thì tối đa mỗi a(i) chỉ bị tác động 7 - 8 lần
  14. // Update 1 vị trí tương đương update một nút lá trong cây Segment Tree, mỗi lần update tốn O(log)
  15. // => Mỗi nút lá tối đa tốn O(8 * log) chi phí update
  16. // => Update cả mảng thì tối đa tốn O(8 * nlogn)
  17. // => Độ phức tạp O(qlogn + nlogn) = O((q + n)logn)
  18.  
  19. struct node {
  20. 	int mx; 
  21. 	ll sum;
  22.  
  23. 	node() {
  24. 		mx = -INF, sum = 0;  
  25. 	}
  26.  
  27. 	node(int x) {
  28. 		mx = sum = x;  
  29. 	}
  30.  
  31. 	node operator+(const node& other) const {
  32. 		node c;  
  33. 		c.mx = max(mx, other.mx); 
  34. 		c.sum = sum + other.sum; 
  35. 		return c; 
  36. 	}
  37. }; 
  38.  
  39. int n, q; 
  40. int a[N]; 
  41. int D[MAX_A]; 
  42.  
  43. void sieve() {
  44. 	for (int i = 1; i < MAX_A; i++) {
  45. 		for (int j = i; j < MAX_A; j += i) D[j]++; 
  46. 	}
  47. }
  48.  
  49. node seg[4 * N]; 
  50.  
  51. void build(int id, int l, int r) {
  52. 	if (l == r) {
  53. 		seg[id] = node(a[l]);  
  54. 		return; 
  55. 	}
  56. 	int mid = (l + r) >> 1; 
  57. 	build(id * 2, l, mid); 
  58. 	build(id * 2 + 1, mid + 1, r); 
  59. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  60. }
  61.  
  62. // Để check một nút có cần được update nữa hay k thì ta quan tâm giá trị max của đoạn [l, r] mà nó quản lí
  63. // max <= 2 thì coi như k cần update nữa 
  64. void update(int id, int l, int r, int u, int v) {
  65. 	if (l > v || r < u) return;  
  66.  
  67. 	if (seg[id].mx <= 2) return; 
  68.  
  69. 	if (l == r) {
  70. 		a[l] = D[a[l]];  
  71. 		seg[id] = a[l]; 
  72. 		return;  
  73. 	}
  74.  
  75. 	int mid = (l + r) >> 1; 
  76. 	update(id * 2, l, mid, u, v); 
  77. 	update(id * 2 + 1, mid + 1, r, u, v); 
  78.  
  79. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  80. }
  81.  
  82. node get(int id, int l, int r, int u, int v) {
  83. 	if (l > v || r < u) return node(); 
  84.  
  85. 	if (u <= l && r <= v) return seg[id]; 
  86.  
  87. 	int mid = (l + r) >> 1; 
  88. 	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  89. }
  90.  
  91. int main() {
  92. 	ios::sync_with_stdio(0); cin.tie(0);  	
  93. 	cin >> n >> q; 
  94. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  95.  
  96. 	sieve();   
  97.  
  98. 	build(1, 1, n); 
  99.  
  100. 	while (q--) {
  101. 		int type, l, r; 
  102. 		cin >> type >> l >> r; 
  103.  
  104. 		if (type == 1) {
  105. 			update(1, 1, n, l, r); 
  106. 		}
  107. 		else {
  108. 			cout << get(1, 1, n, l, r).sum << '\n'; 
  109. 		}
  110. 	}
  111. }
Success #stdin #stdout 0.03s 26888KB
comments (?)
stdin
copy 
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
stdout
copy 
30
13
4
22
https://ideone.com/rlJvuX
language:
C++14 (gcc 8.3)
created:
1 year 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!