2094.md (23028B)
1 Source: https://codeforces.com/blog/entry/141796 2 3 **Rating Predictions** 4 5 | Predictor | A | B | C | D | E | F | G | H | 6 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 800 | 800 | 1000 | 1200 | 1300 | 1600 | 1800 | 8 | [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") | 800 | 800 | 800 | 900 | 1200 | 1200 | 1600 | 1600 | 9 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 800 | 800 | 900 | 1500 | 1500 | 1700 | 1700 | 10 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 800 | 800 | 900 | 1600 | 900 | 1800 | — | 11 | [Filikec](/profile/Filikec "Expert Filikec") | 800 | 800 | 800 | 900 | 1300 | 1500 | 1700 | 1800 | 12 | [Edeeva](/profile/Edeeva "Master Edeeva") | 800 | 800 | 800 | 1000 | 1300 | 1600 | 1700 | 1900 | 13 | [yoru_sacri](/profile/yoru_sacri "Candidate Master yoru_sacri") | 800 | 800 | 800 | 900 | 1400 | 1700 | 1900 | 1900 | 14 | [kevlu8](/profile/kevlu8 "Expert kevlu8") | 800 | 800 | 800 | 900 | 1600 | 1400 | 1700 | — | 15 | [AG-88301](/profile/AG-88301 "Specialist AG-88301") | 800 | 800 | 800 | 800 | 1400 | 1500 | — | — | 16 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 800 | 1000 | 1300 | 1200 | 1800 | 2000 | 17 | [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv") | 800 | 800 | 800 | 1000 | 1200 | 3500 | 1900 | 2000 | 18 | [temporary1](/profile/temporary1 "Master temporary1") | 800 | 800 | 800 | 1000 | 1400 | 1500 | 1500 | 2000 | 19 20 Thanks to [reirugan](/profile/reirugan "Candidate Master reirugan") for helping write the editorials. 21 22 #### [2094A - Trippi Troppi](/contest/2094/problem/A "Codeforces Round 1017 (Div. 4)") 23 24 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 25 26 **Solution** 27 28 This can be solved by printing the zero-th index of each string in sequence. For example, suppose your strings are $a$, $b$, and $c$. Then in C++, you can use `cout << a[0] << b[0] << c[0] << '\n';`, and similarly, in Python you can use `print(a[0] + b[0] + c[0])`. See your preferred language's syntax for how to obtain a given indexed character from a string. 29 30 **Code** 31 32 ``` 33 t = int(input()) 34 for _ in range(t): 35 inp = input() 36 for w in inp.split(): 37 print(w[0],end="") 38 print() 39 ``` 40 41 **Rate The Problem!** 42 43 * Good Problem 44 * Okay Problem 45 * Bad Problem 46 * Didn't Solve 47 48 #### [2094B - Bobritto Bandito](/contest/2094/problem/B "Codeforces Round 1017 (Div. 4)") 49 50 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 51 52 **Hint** 53 54 What is the condition for $l'$ and $r'$ to be valid? 55 56 **Answer** 57 58 We must have $r' - l' = m$ and $l\leq l' \leq 0 \leq r'\leq r$. 59 60 **Solution** 61 62 The problem reduces to finding $l'$ and $r'$ such that $r' - l' = m$ and $l\leq l' \leq 0 \leq r'\leq r$. There are several different approaches; two are outlined below. 63 64 One approach which runs in $O(1)$ time is to case on whether $m\leq r$. If $m\leq r$, we can choose $l' = 0$ and $r' = m$, and then we see that $r' - l' = m - 0 = m$ and $l \leq 0 \leq 0 \leq m \leq r$ as desired. If $m \gt r$, we can choose $l' = r-m$ and $r' = r$, and then we see that $r' - l' = r - (r-m) = m$ and $l \leq r-m \leq 0 \leq r \leq r$, where $l \leq r-m$ holds because $r-l = n \geq m$. 65 66 An alternative approach which runs in $O(m)$ time is to simply simulate the process; expand in an arbitrary direction which satisfies the desired inequalities until $r' - l' = m$. 67 68 **Code** 69 70 ``` 71 #include <bits/stdc++.h> 72 using namespace std; 73 #define int long long 74 75 void solve() { 76 int n, m, l, r; cin >> n >> m >> l >> r; 77 int diff = n - m; 78 l = abs(l); 79 if (l >= diff) { 80 l -= diff; 81 diff = 0; 82 } 83 else { 84 diff -= l; 85 l = 0; 86 } 87 cout << -l << " " << r - diff << '\n'; 88 } 89 90 signed main() { 91 ios_base::sync_with_stdio(0); 92 cin.tie(0); 93 int t; cin >> t; 94 while (t--) solve(); 95 return 0; 96 } 97 ``` 98 99 **Rate The Problem!** 100 101 * Good Problem 102 * Okay Problem 103 * Bad Problem 104 * Didn't Solve 105 106 #### [2094C - Brr Brrr Patapim](/contest/2094/problem/C "Codeforces Round 1017 (Div. 4)") 107 108 Problem Credits: [cry](/profile/cry "International Master cry") 109 110 **Hint** 111 112 How can we find $p_i$ for $2\leq i\leq n$? How can we find $p_i$ for $n+1\leq i\leq 2n$? 113 114 **Answer** 115 116 For $2\leq i\leq n$, we can find $p_i$ by checking $G_{1, i-1}$. For $n+1\leq i\leq 2n$, we can find $p_i$ by checking $G_{n, i-n}$. 117 118 **Solution** 119 120 Observe that for all $2\leq i\leq n$, we can find $p_i$ by checking $G_{1, i-1}$. Then for all $n+1\leq i\leq 2n$, we can find $p_i$ by checking $G_{n, i-n}$. Now, we only have to find the value of $p_1$. However, each value from $1$ to $2n$ must appear exactly once in $p$. Thus, we can simply find the value which has not appeared yet, and choose that as $p_1$. This can be done by storing which values have been seen in a boolean array, and then finding which one remains false. 121 122 **Code** 123 124 ``` 125 #include <bits/stdc++.h> 126 using namespace std; 127 #define int long long 128 129 void solve() { 130 int n; cin >> n; 131 vector<int> ans(2*n+1, 0); 132 vector<bool> used(2*n+1, false); 133 for (int i = 1; i <= n; i++) { 134 for (int j = 1; j <= n; j++) { 135 int x; cin >> x; 136 ans[i + j] = x; 137 used[x] = true; 138 } 139 } 140 for (int i = 1; i <= 2 * n; i++) { 141 if (ans[i] != 0) cout << ans[i] << " "; 142 else { 143 for (int j = 1; j <= n * 2; j++) { 144 if (!used[j]) { 145 used[j] = true; 146 cout << j << " "; 147 break; 148 } 149 } 150 } 151 } 152 cout << "\n"; 153 } 154 155 signed main() { 156 ios_base::sync_with_stdio(0); 157 cin.tie(0); 158 int t; cin >> t; 159 while (t--) solve(); 160 return 0; 161 } 162 ``` 163 164 **Rate The Problem!** 165 166 * Good Problem 167 * Okay Problem 168 * Bad Problem 169 * Didn't Solve 170 171 #### [2094D - Tung Tung Sahur](/contest/2094/problem/D "Codeforces Round 1017 (Div. 4)") 172 173 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 174 175 **Hint** 176 177 What would happen if $s_1$ consists of only $L$? 178 179 **Answer** 180 181 In this case, the answer is yes if and only if $|s_1| \leq |s_2| \leq 2|s_1|$. Now try to generalize this. 182 183 **Solution** 184 185 First, let us consider a simpler case of the problem: suppose that there is only $L$ in both $s_1$ and $s_2$. Then it is clear that the answer is yes if and only if $|s_1| \leq |s_2| \leq 2|s_1|$. If this holds (in particular, we also necessitate that $s_1$ and $s_2$ consist of only a single character, and the same character), we will call $s_2$ an extension of $s_1$. 186 187 Now, observe that the problem given is simply the simpler version, repeated several times alternating between $L$ and $R$. So we can partition $s_1$ into "blocks" (where we define a block to be a maximal group of contiguous identical characters). Then the answer is yes if and only if $s_2$ is the concatenation of extensions of blocks in $s_1$. For example, consider $s_1 = LLLLLRL$. We see that this consists of five $L$s, one $R$, and one $L$. So the answer is yes if and only if $s_2$ consists of between five and ten $L$s (inclusive), between one and two $R$s, and between one and two $L$ 's, concatenated in that order. 188 189 **Code** 190 191 ``` 192 #include <bits/stdc++.h> 193 using namespace std; 194 #define int long long 195 196 void solve() { 197 string a, b; cin >> a >> b; 198 int n = a.size(); 199 int m = b.size(); 200 if (m < n || m > 2 * n || a[0] != b[0]) { 201 cout << "NO\n"; 202 return; 203 } 204 vector<int> aa, bb; 205 int cnt = 1; 206 for (int i = 1; i < n; i++) { 207 if (a[i] != a[i-1]) { 208 aa.push_back(cnt); 209 cnt = 1; 210 } 211 else cnt++; 212 } 213 aa.push_back(cnt); 214 cnt = 1; 215 for (int i = 1; i < m; i++) { 216 if (b[i] != b[i-1]) { 217 bb.push_back(cnt); 218 cnt = 1; 219 } 220 else cnt++; 221 } 222 bb.push_back(cnt); 223 if (aa.size() != bb.size()) { 224 cout << "NO\n"; 225 return; 226 } 227 n = aa.size(); 228 for (int i = 0; i < n; i++) { 229 if (aa[i] > bb[i] || aa[i] * 2 < bb[i]) { 230 cout << "NO\n"; 231 return; 232 } 233 } 234 cout << "YES\n"; 235 } 236 237 signed main() { 238 ios_base::sync_with_stdio(0); 239 cin.tie(0); 240 int t; cin >> t; 241 while (t--) solve(); 242 return 0; 243 } 244 ``` 245 246 **Rate The Problem!** 247 248 * Good Problem 249 * Okay Problem 250 * Bad Problem 251 * Didn't Solve 252 253 #### [2094E - Boneca Ambalabu](/contest/2094/problem/E "Codeforces Round 1017 (Div. 4)") 254 255 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 256 257 **Hint 1** 258 259 Consider each bit independently. 260 261 **Hint 2** 262 263 Suppose we fix $k$. How can we compute the desired sum quickly? Note that this may require preprocessing. 264 265 **Solution** 266 267 Here, it suffices to consider each bit independently, because addition is both commutative and associative. For $0\leq i \lt 30$, let $cnt_i$ denote the number of elements of $a$ which have the $i$-th bit set (where bits are indexed from the least significant bit being the $0$-th bit); note that these can be found in $O(30n)$ time (more generally, we need $O(\log\max{a_i})$ operations per element). 268 269 Now, suppose we choose a particular $k$. Then we can find the sum $(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$ as follows: for a given bit position $i$, the number of elements $a_j$ such that $a_k \oplus a_j$ has the $i$-th bit set will be $cnt_i$ if the $i$-th bit of $a_k$ is not set, and $n-cnt_i$ if the $i$-th bit of $a_k$ is set. So we can simply add $cnt_i \cdot 2^i$ to our sum if the $i$-th bit of $a_k$ is not set, and add $(n-cnt_i) \cdot 2^i$ to our sum if the $i$-th bit of $a_k$ is set. 270 271 This allows us to compute $(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$ for any $k$ in $O(30)$ time, so we can now compute this sum for all $k$ in $O(30n)$ time and output the maximum. 272 273 **Code** 274 275 ``` 276 #include <bits/stdc++.h> 277 using namespace std; 278 #define int long long 279 280 void solve() { 281 int n; cin >> n; 282 int arr[n+1]; 283 vector<int> cnt(30, 0); 284 for (int i = 1; i <= n; i++) { 285 cin >> arr[i]; 286 for (int j = 0; j < 30; j++) { 287 cnt[j] += ((arr[i] >> j) & 1); 288 } 289 } 290 int ans = 0; 291 for (int i = 1; i <= n; i++) { 292 int tot = 0; 293 for (int j = 0; j < 30; j++) { 294 bool f = ((arr[i] >> j) & 1); 295 if (f) tot += (1 << j) * (n - cnt[j]); 296 else tot += (1 << j) * cnt[j]; 297 } 298 ans = max(ans, tot); 299 } 300 cout << ans << "\n"; 301 } 302 303 signed main() { 304 ios_base::sync_with_stdio(0); 305 cin.tie(0); 306 int t; cin >> t; 307 while (t--) solve(); 308 return 0; 309 } 310 ``` 311 312 **Rate The Problem!** 313 314 * Good Problem 315 * Okay Problem 316 * Bad Problem 317 * Didn't Solve 318 319 #### [2094F - Trulimero Trulicina](/contest/2094/problem/F "Codeforces Round 1017 (Div. 4)") 320 321 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 322 323 **Hint** 324 325 What would happen if we tried outputting the numbers $1, \dots, k, 1, \dots, k, \dots$ in the natural reading order? For example, for $n=3$, $m=4$, and $k=6$, we would output the following: 326 327 | | | | | 328 | --- | --- | --- | --- | 329 | 1 | 2 | 3 | 4 | 330 | 5 | 6 | 1 | 2 | 331 | 3 | 4 | 5 | 6 | 332 333 In which cases does this fail? 334 335 **Answer** 336 337 This fails if and only if $m$ is a multiple of $k$, because we see that horizontally adjacent elements differ by $1\pmod k$ and vertically adjacent elements differ by $m\pmod k$. Now try to resolve this case. 338 339 **Solution** 340 341 There are many working constructions for this problem; one of them is to case on whether or not $m$ is a multiple of $k$. 342 343 Suppose $m$ is not a multiple of $k$. For example, consider the second sample, where $n=3$, $m=4$, and $k=6$. Then we can output the numbers $1, \dots, k, 1, \dots, k, \dots$ in the natural reading order, as follows: 344 345 | | | | | 346 | --- | --- | --- | --- | 347 | 1 | 2 | 3 | 4 | 348 | 5 | 6 | 1 | 2 | 349 | 3 | 4 | 5 | 6 | 350 351 and we see that any two horizontally adjacent elements differ by $1\pmod k$, whereas any two vertically adjacent elements differ by $m\pmod k$, so no two adjacent elements are the same, as desired. 352 353 Now, suppose $m$ is a multiple of $k$. For example, consider the case $n=4$, $m=6$, and $k=3$. Suppose we were to try the above strategy, then we get: 354 355 | | | | | | | 356 | --- | --- | --- | --- | --- | --- | 357 | 1 | 2 | 3 | 1 | 2 | 3 | 358 | 1 | 2 | 3 | 1 | 2 | 3 | 359 | 1 | 2 | 3 | 1 | 2 | 3 | 360 | 1 | 2 | 3 | 1 | 2 | 3 | 361 362 which doesn't work, since vertically adjacent elements are the same. We can fix this by cyclically shifting every other row as follows: 363 364 | | | | | | | 365 | --- | --- | --- | --- | --- | --- | 366 | 1 | 2 | 3 | 1 | 2 | 3 | 367 | 2 | 3 | 1 | 2 | 3 | 1 | 368 | 1 | 2 | 3 | 1 | 2 | 3 | 369 | 2 | 3 | 1 | 2 | 3 | 1 | 370 371 and we see that any two horizontally adjacent elements differ by $1\pmod k$ as before, whereas any two vertically adjacent elements also differ by $1\pmod k$, so no two adjacent elements are the same, as desired. 372 373 **Code** 374 375 ``` 376 import sys 377 input = sys.stdin.readline 378 for _ in range(int(input())): 379 n,m,k = map(int,input().split()) 380 LAST = [-1 for _ in range(m)] 381 for i in range(n): 382 shift = False 383 CUR = [0 for _ in range(m)] 384 for j in range(m): 385 elm = ((i * m + j) % k) + 1 386 if elm == LAST[j]: 387 shift = True 388 CUR[j] = elm 389 if shift: 390 CUR = [CUR[(j+1)%m] for j in range(m)] 391 print(*CUR) 392 LAST = CUR 393 ``` 394 395 **Rate The Problem!** 396 397 * Good Problem 398 * Okay Problem 399 * Bad Problem 400 * Didn't Solve 401 402 #### [2094G - Chimpanzini Bananini](/contest/2094/problem/G "Codeforces Round 1017 (Div. 4)") 403 404 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED"), [cry](/profile/cry "International Master cry") 405 406 **Hint 1** 407 408 Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front. Thus, we would like to push elements to both ends of the array. What data structure supports this? 409 410 **Answer** 411 412 A deque is the most natural choice to use. Most languages, including C++, Java, and Python, include deques in their standard library, so you likely do not have to implement it yourself. 413 414 **Hint 2** 415 416 What other values do we need to maintain in order to keep track of score? 417 418 **Answer** 419 420 It suffices to keep track of the current score, the score of the array if it were backwards, the size of the array, and the sum of the array. 421 422 **Solution** 423 424 We can solve this using a deque. Let $score$ denote the current score, and $rscore$ denote the score of the array if it were backwards. Let $size$ denote the size of the array, and $sum$ denote the sum of the array. Then we consider how these three values change as each operation is performed. 425 426 Suppose operation 1 is performed. This is equivalent to popping the back element of the array and pushing it in the front. When you pop the back element of the array, $score$ decreases by $a_n \cdot size$. Then when you push it to the front, $score$ increases by $sum$ because $a_n$ is pushed to the first spot and every element from $a_1$ to $a_{n-1}$ moves forward one spot. Notice that $rscore$ changes in the reverse way; this is equivalent to popping the front element of the array and pushing it to the back. When you pop the front element of the array, $rscore$ decreases by $sum$, and when you push it to the back, $rscore$ increases by $a_n \cdot size$. Note that $size$ and $sum$ remain unchanged. 427 428 Suppose operation 2 is performed. Then we swap $score$ and $rscore$, and we also want to "reverse" the array. However, it is costly to entirely reverse the deque. Instead, we will set a flag to indicate that the array has been reversed (and similarly, if the flag is already set, we will unset it). If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3. 429 430 Suppose operation 3 is performed. Then we see that $size$ increases by $1$ and $sum$ increases by $k$. Then $score$ increases by $k \cdot size$ and $rscore$ increases by $sum$ (using the new value of $sum$), by identical reasoning to that in operation 1. 431 432 Additional optimization: we don't actually have to maintain $rscore$; we can obtain it with the expression: $(n+1)\sum_{i=1}^na_i-score$. This is because $score + rscore = (n+1)\sum_{i=1}^na_i$ since the $i$-th term is counted $i$ times in $score$ and $n+1-i$ times in $rscore$. 433 434 **Code** 435 436 ``` 437 #include <bits/stdc++.h> 438 using namespace std; 439 #define int long long 440 441 void solve() { 442 int norm = 0, rev = 0; 443 int q; cin >> q; 444 int tot = 0; 445 int n = 0; 446 deque<int> qNorm, qRev; 447 int p = 0; 448 while (q--) { 449 int s; cin >> s; 450 if (s == 1) { 451 int last = qNorm.back(); 452 qNorm.pop_back(); 453 qNorm.push_front(last); 454 norm += (tot - last); 455 norm -= last * n; 456 norm += last; 457 458 last = qRev.front(); 459 qRev.pop_front(); 460 qRev.push_back(last); 461 rev -= (tot - last); 462 rev += last * n; 463 rev -= last; 464 } 465 else if (s == 2) { 466 swap(rev, norm); 467 swap(qNorm, qRev); 468 } 469 else if (s == 3) { 470 n++; 471 int k; cin >> k; 472 qNorm.push_back(k); 473 qRev.push_front(k); 474 norm += k * n; 475 rev += tot; 476 rev += k; 477 tot += k; 478 } 479 cout << norm << "\n"; 480 } 481 } 482 483 signed main() { 484 ios_base::sync_with_stdio(0); 485 cin.tie(0); 486 int t; cin >> t; 487 while (t--) solve(); 488 return 0; 489 } 490 ``` 491 492 **Rate The Problem!** 493 494 * Good Problem 495 * Okay Problem 496 * Bad Problem 497 * Didn't Solve 498 499 #### [2094H - La Vaca Saturno Saturnita](/contest/2094/problem/H "Codeforces Round 1017 (Div. 4)") 500 501 Problem Credits: [cry](/profile/cry "International Master cry") 502 503 **Hint 1** 504 505 What must the value of $a[i]$ be in order for $k$ to change? 506 507 **Answer** 508 509 $a[i]$ must be a divisor of $k$. 510 511 **Hint 2** 512 513 Can we use this to bound the number of times $k$ changes? 514 515 **Answer** 516 517 For each divisor $d$ of $k$, $k$ can only change once, because after the first iteration with $a[i] = d$, $k$ is no longer divisible by $d$. Thus, the number of times $k$ changes is bounded by the number of divisors of $k$. 518 519 **Solution** 520 521 Consider a particular query. We make the following two observations: first, the value of $k$ only changes if $a[i]$ is a divisor of $k$, and second, if there exists $a[i_1] = a[i_2]$ with $l\leq i_1 \lt i_2 \leq r$, then the value of $k$ will not change at $i=i_2$ (because after the iteration $i=i_1$, we have that $k$ is no longer divisible by $a[i_2]$). 522 523 This allows us to bound the number of times $k$ changes by $d(k)$, where $d(k)$ is the number of divisors of $k$. Note that the divisors of $d(k)$ can be found in $O(\sqrt{k})$ time by checking if $a$ divides $k$ for every $a$ from $2$ to $\sqrt{k}$, and if so, $a$ and $\frac{k}{a}$ are both divisors of $k$. Furthermore, at the scale constrained by the problem bounds, $d(k)$ is around $O(\sqrt[3]{k})$, so we only have to update $k$ at most $O(\sqrt[3]{k})$ times. 524 525 Now, we would like to find the first time each divisor of $k$ appears in $a[l], \dots, a[r]$. This can be done by storing the array $a$ in a map, where each value is mapped to a vector of indices where that values appears. Then for a given divisor of $k$, we can use `lower_bound()` (or generally, binary search) to find the smallest index at or after $l$ where this divisor appears, and we can check if it is no greater than $r$. 526 527 Now, we have a list of indices at which $k$ might change. So, suppose that $k$ changes to $k'$ at index $i_1$, and then changes to $k' '$ at index $i_2$ (and these are adjacent changes). Then we know that we have a value of $k'$ from $i=i_1$ to $i_2-1$, so we can add $k' \cdot (i_2 - i_1)$ to $ans$. We can then do this for all changes. This allows us to solve the problem in $O(n\log{n})$ preprocessing time and $O(\sqrt{k} + d(k)\log{n})$ time per query. 528 529 There are a few ways to optimize the runtime further, if your implementation is too slow. We can use a vector (of vectors) instead of a map, since $A = \max a_i = 10^5$ is reasonably small. Note that instantiating a vector of this size in every test case is too slow, so you may have to instantiate it globally and clear the vectors that were used after each test case. 530 531 Another optimization is to preprocess divisors instead of computing them on the spot. We can compute and store the divisors of all integers $2\leq a_i\leq 10^5$ in $O(A\log A)$ time in a vector of vectors where $divisor[a_i]$ contains all divisors of $a_i$ as follows: for all $2\leq i\leq A$, we push $i$ into $divisors[j]$ for all multiples $j$ of $i$. (The runtime follows from the fact that there are $\lfloor\frac{A}{i}\rfloor$ multiples of $i$ which are at most $A$, so across all $i$, we have at most $\frac{A}{1} + \frac{A}{2} + \cdots + \frac{A}{A} = A(\frac{1}{1} + \cdots + \frac{1}{A}) = AH(A) = O(A\log A)$ computations). This allows us to remove the $\sqrt{k}$ term in the runtime of each query. 532 533 **Code** 534 535 ``` 536 #include <bits/stdc++.h> 537 using namespace std; 538 #define int long long 539 540 void solve() { 541 map<int, vector<int>> pos; 542 map<int, int> ptr; 543 int n, q; cin >> n >> q; 544 int arr[n+1]; 545 for (int i = 1; i <= n; i++) { 546 cin >> arr[i]; 547 pos[arr[i]].push_back(i); 548 ptr[arr[i]] = 0; 549 } 550 vector<tuple<int, int, int, int>> qr(q); 551 int c = 0; 552 for (auto &[l, r, v, i]: qr) { 553 cin >> v >> l >> r; 554 i = c++; 555 } 556 vector<int> anss(q); 557 sort(qr.begin(), qr.end()); 558 int prevL = 1; 559 for (auto [l, r, v, idd]: qr) { 560 for (int j = prevL; j < l; j++) { 561 ptr[arr[j]]++; 562 } 563 prevL = l; 564 vector<pair<int, int>> facts; 565 for (int i = 1; i * i <= v; i++) { 566 if (v % i == 0) { 567 int fact1 = v / i; 568 if (!(pos[fact1].size() == 0 || ptr[fact1] >= pos[fact1].size() || pos[fact1][ptr[fact1]] > r || fact1 == 1)) { 569 facts.push_back({pos[fact1][ptr[fact1]], fact1}); 570 } 571 int fact2 = i; 572 if (fact2 == fact1) continue; 573 if (!(pos[fact2].size() == 0 || ptr[fact2] >= pos[fact2].size() || pos[fact2][ptr[fact2]] > r || fact2 == 1)) { 574 facts.push_back({pos[fact2][ptr[fact2]], fact2}); 575 } 576 } 577 } 578 sort(facts.begin(), facts.end()); 579 int pr = l; 580 int ans = 0; 581 for (auto [idx, val]: facts) { 582 int rr = idx - pr; 583 ans += v * rr; 584 while (v % val == 0) v /= val; 585 pr = idx; 586 } 587 if (facts.empty()) ans = v * (r - l + 1); 588 else ans += (r - pr + 1) * v; 589 anss[idd] = ans; 590 } 591 for (int i = 0; i < q; i++) cout << anss[i] << "\n"; 592 } 593 594 signed main() { 595 ios_base::sync_with_stdio(0); 596 cin.tie(0); 597 int t; cin >> t; 598 while (t--) solve(); 599 return 0; 600 } 601 ``` 602 603 **Rate The Problem!** 604 605 * Good Problem 606 * Okay Problem 607 * Bad Problem 608 * Didn't Solve