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