2153.md (35433B)
1 Source: https://codeforces.com/blog/entry/147264 2 3 ### [2153A - Circle of Apple Trees](/contest/2153/problem/A "Codeforces Round 1057 (Div. 2)") 4 5 **Hint 1** 6 7 You can't eat two apples of the same beauty value. 8 9 **Hint 2** 10 11 Is there a way to eat apples of all kinds of beauty values that appearred? 12 13 **Solution** 14 15 First of all, since the beauty values of the apples you eat are in strictly increasing order, any two of them have different beauty values. 16 17 So, for each beauty value, you can eat at most one apple. 18 19 In fact, it can be shown that it is always possible to eat exactly one apple of each beauty value. Let's say all the distinct beauty values are $v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$. You can eat one apple of beauty value $v_i$ during the $i$-th time you move along the full circle. 20 21 Therefore, the answer is the number of distinct numbers in beauty values. The time complexity is $\mathcal{O}(n)$. 22 23 **Code (C++, maomao90)** 24 25 ``` 26 #include <bits/stdc++.h> 27 using namespace std; 28 29 int t, n; 30 31 int main() { 32 cin >> t; 33 34 while (t--) { 35 cin >> n; 36 37 set<int> st; 38 for (int i = 0; i < n; i++) { 39 int x; 40 cin >> x; 41 st.insert(x); 42 } 43 44 cout << (int) st.size() << '\n'; 45 } 46 47 return 0; 48 } 49 ``` 50 51 **Code (Pypy3.10, Little_Sheep_Yawn)** 52 53 ``` 54 import sys 55 input = lambda: sys.stdin.readline().strip() 56 57 t = int(input()) 58 outs = [] 59 60 for _ in range(t): 61 n = int(input()) 62 nums = list(map(int, input().split())) 63 # There can be hash collisions, but n is small enough. 64 outs.append(len(set(nums))) 65 66 print('\n'.join(map(str, outs))) 67 ``` 68 69 ### [2153B - Bitwise Reversion](/contest/2153/problem/B "Codeforces Round 1057 (Div. 2)") 70 71 **Hint** 72 73 Consider each bit of the numbers separately. 74 75 **Solution** 76 77 Different bits don't interfere with one another when you do bitwise operations. So, for each bit $k$, we can iterate over $2^3$ possibilities of $a_k = \mathtt{0} \text{ or } \mathtt{1}$, $b_k = \mathtt{0} \text{ or } \mathtt{1}$, and $c_k = \mathtt{0} \text{ or } \mathtt{1}$, and check whether it is consistent with the given numbers. 78 79 The time complexity for each test case is $\mathcal{O}(\log \max(x, y, z))$. 80 81 **Code (C++, maomao90)** 82 83 ``` 84 #include <bits/stdc++.h> 85 using namespace std; 86 87 using ll = long long; 88 89 const int MAXL = 60; 90 91 int t; 92 ll x, y, z; 93 94 int main() { 95 cin >> t; 96 while (t--) { 97 cin >> x >> y >> z; 98 ll a = 0, b = 0, c = 0; 99 bool ans = true; 100 for (int l = MAXL - 1; l >= 0; l--) { 101 ll bit_x = x >> l & 1, bit_y = y >> l & 1, bit_z = z >> l & 1; 102 bool found = false; 103 for (ll bit_a : {0, 1}) { 104 for (ll bit_b : {0, 1}) { 105 for (ll bit_c : {0, 1}) { 106 if ((bit_a & bit_b) == bit_x && 107 (bit_b & bit_c) == bit_y && 108 (bit_a & bit_c) == bit_z) { 109 found = true; 110 a |= bit_a << l; 111 b |= bit_b << l; 112 c |= bit_c << l; 113 break; 114 } 115 } 116 if (found) { 117 break; 118 } 119 } 120 if (found) { 121 break; 122 } 123 } 124 if (!found) { 125 ans = false; 126 break; 127 } 128 } 129 if (!ans) { 130 cout << "NO\n"; 131 } else { 132 assert((a & b) == x); 133 assert((b & c) == y); 134 assert((a & c) == z); 135 cout << "YES\n"; 136 } 137 } 138 return 0; 139 } 140 ``` 141 142 **Code (Pypy3.10, Little_Sheep_Yawn, using the bonus)** 143 144 ``` 145 import sys 146 input = lambda: sys.stdin.readline().strip() 147 148 t = int(input()) 149 outs = [] 150 151 for _ in range(t): 152 x, y, z = map(int, input().split()) 153 154 a = x | z 155 b = x | y 156 c = y | z 157 158 outs.append('YES' if a & b == x and b & c == y and a & c == z else 'NO') 159 160 print('\n'.join(outs)) 161 ``` 162 163 **Bonus** 164 165 You just need to check whether $(a,b,c)=(x|z,x|y,y|z)$ is a valid solution, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). Why? 166 167 ### [2153C - Symmetrical Polygons](/contest/2153/problem/C "Codeforces Round 1057 (Div. 2)") 168 169 **Hint 1** 170 171 Consider the line of symmetry. It intersects with the polygon at no more than $2$ sticks if we don't consider the endpoints of the sides. 172 173 **Hint 2** 174 175 Other sticks come in pairs. 176 177 **Solution** 178 179 Any line intersects with the polygon at no more than $2$ sticks (Here, we don't consider the endpoints of the sides when talking about intersection). 180 181 Consider the line of symmetry. The sticks not intersecting with it come in pairs of the same length. 182 183 Once we group the sticks in pairs of the same length (some sticks are not grouped), we should always use all of the pairs to construct the symmetrical convex polygon. 184 185 That is because, if we do not use all the pairs, for each unchosen pair, we can always add a copy of the stick on each side of the line of symmetry, which enlarges the perimeter. And if there exists a pair which we only use one of them as a side, it has to intersects with the line of symmetry. We can replace it with the pair on both sides of the line of symmetry and make the polygon convex with a larger perimeter. 186 187 **Case 1:** The line of symmetry intersects none of the sticks. 188 189 Only pairs of sticks with same length can be used. To obtain the largest perimeter, it is the most optimal to use all possible pairs. 190 191 **Case 2:** The line of symmetry intersects exactly one stick. 192 193 Let us call the stick that intersects the line of symmetry the *odd* stick. As long as the length of the odd stick is less than the total length of the pairs of sticks with identical length, we can use the odd stick. Hence, we can iterate through all possible sticks and check whether it is possible for it to be the odd stick in $O(1)$ time for each odd stick. 194 195 **Case 3:** The line of symmetry intersects exactly two sticks. 196 197 Let the longer of the two sticks that intersect the line of symmetry be the *long odd* stick, and the shorter be the *short odd* stick. As long as the difference in the length of the long odd stick and even odd stick is less than the total length of the pairs of sticks with identical length, we can use the long odd stick and short odd stick. 198 199 Let's say the remaining sticks in ascending order are $v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$. If the longer stick we choose is $v_i\ (i\gt 1)$, then the shorter one we choose should always be $v_{i-1}$, because it is the longest one we can choose and the difference of the two sticks chosen is minimized. 200 201 So you just need to check these pairs: $(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$. 202 203 The time complexity is $\mathcal{O}(n\log n)$. 204 205 **Code (C++, maomao90)** 206 207 ``` 208 #include <bits/stdc++.h> 209 using namespace std; 210 211 using ll = long long; 212 213 const int MAXN = 200'005; 214 215 int t; 216 int n; 217 int a[MAXN]; 218 map<int, int> cnt; 219 220 int main() { 221 ios::sync_with_stdio(0), cin.tie(0); 222 cin >> t; 223 while (t--) { 224 cnt.clear(); 225 226 cin >> n; 227 for (int i = 0; i < n; i++) { 228 cin >> a[i]; 229 } 230 for (int i = 0; i < n; i++) { 231 cnt[a[i]]++; 232 } 233 234 ll base = 0; 235 vector<int> odd, even; 236 for (auto [x, c] : cnt) { 237 base += (ll)x * (c / 2); 238 if (c % 2 == 1) { 239 odd.push_back(x); 240 } else if (c >= 2) { 241 even.push_back(x); 242 } 243 } 244 245 if (base == 0) { 246 cout << 0 << '\n'; 247 continue; 248 } 249 250 ll ans = 0; 251 for (int x : odd) { 252 if (2 * base > x) { 253 ans = max(ans, 2 * base + x); 254 } 255 } 256 257 assert(is_sorted(odd.begin(), odd.end())); 258 for (int i = 1; i < (int)odd.size(); i++) { 259 if (odd[i - 1] + 2 * base > odd[i]) { 260 ans = max(ans, odd[i - 1] + 2 * base + odd[i]); 261 } 262 } 263 264 for (int x : even) { 265 if (base - x > 0) { 266 ans = max(ans, 2 * base); 267 } 268 } 269 270 cout << ans << '\n'; 271 } 272 return 0; 273 } 274 ``` 275 276 **Code (Pypy3.10, Little_Sheep_Yawn)** 277 278 ``` 279 import sys 280 input = lambda: sys.stdin.readline().strip() 281 282 t = int(input()) 283 outs = [] 284 285 # avoiding hash collisions, which we don't have tests in the pretests 286 rnd = random.getrandbits(30) 287 fmax = lambda x, y: x if x > y else y 288 289 for _ in range(t): 290 n = int(input()) 291 nums = list(map(int, input().split())) 292 293 cnt = Counter(x ^ rnd for x in nums) 294 295 c = 0 296 half = 0 297 tmp = [] 298 299 for x in cnt: 300 if cnt[x] > 1: 301 c += cnt[x] // 2 302 half += cnt[x] // 2 * (x ^ rnd) 303 if cnt[x] % 2: 304 tmp.append(x ^ rnd) 305 306 tmp.sort() 307 308 ans = 0 if c <= 1 else half * 2 309 310 for x in tmp: 311 if half * 2 > x: 312 ans = fmax(ans, half * 2 + x) 313 314 for i in range(1, len(tmp)): 315 if half * 2 > tmp[i] - tmp[i - 1]: 316 ans = fmax(ans, half * 2 + tmp[i - 1] + tmp[i]) 317 318 outs.append(ans) 319 320 print('\n'.join(map(str, outs))) 321 ``` 322 323 ### [2153D - Not Alone](/contest/2153/problem/D "Codeforces Round 1057 (Div. 2)") 324 325 **Hint 1** 326 327 Break up a nice array into "blocks" of same values. 328 329 **Hint 2** 330 331 Each block can be considered as blocks of size $2$ and $3$ concatenating together. 332 333 **Solution** 334 335 We can divide the nice circular array in blocks, where each block consists of equal values. 336 337 The final circular array can be divided into blocks with size of at least $2$. 338 339 And, since $2=2,3=3,4=2+2$, each block can be divided into sub-blocks of size $2$ and $3$: 340 341 * If the block is of size $3k-1\ (k\gt 0)$, then $3k-1=1\cdot 2+(k-1)\cdot 3$. 342 * If the block is of size $3k\ (k\gt 0)$, then $3k=0\cdot 2+k\cdot 3$. 343 * If the block is of size $3k+1\ (k\gt 0)$, then $3k+1=2\cdot 2+(k-1)\cdot 3$. 344 345 With this observation, we can modify the condition of a nice circular array as follows: 346 347 > A circular array is nice if we can split it into contiguous blocks of length 2 or length 3, such that each block has equal value, and each element belongs to exactly one block. 348 349 Let us first try to solve the easier problem where the array is not circular. Let $\text{dp}[i]$ be the minimum number of operations to make $[a_1,a_2,\ldots,a_i]$ nice. Then, by considering whether the last block containing $a_i$ is of length $2$ or length $3$, we can come up with the transition: 350 351 $\text{dp}[i] = \min(\text{dp}[i - 2] + \text{cost}(a_{i - 1}, a_i), \text{dp}[i - 3] + \text{cost}(a_{i - 2}, a_{i - 1}, a_i))$ 352 353 where $\text{cost}$ denotes the minimum number of operations to make the elements equal. 354 355 To solve the original problem where the array is circular, we can use the standard technique of splitting the circular array by cutting the circle between $(i, i + 1)$ for each $1\le i\le n$. This will take $\mathcal{O}(n^2)$ time. However, since the length of the blocks do not exceed $3$, we only need to try three splitting points $(1, 2)$, $(2, 3)$, and $(3, 4)$. 356 357 The time complexity is $\mathcal{O}(n)$. 358 359 **Code (C++, maomao90)** 360 361 ``` 362 #include <bits/stdc++.h> 363 using namespace std; 364 365 using ll = long long; 366 367 const ll LINF = 1000000000000000005; 368 const int MAXN = 500005; 369 370 int t; 371 int n; 372 int a[MAXN]; 373 ll dp[MAXN]; 374 375 ll cost(int x, int y) { return abs(x - y); } 376 377 ll cost(int x, int y, int z) { 378 if (x > y) { 379 swap(x, y); 380 } 381 if (y > z) { 382 swap(y, z); 383 } 384 if (x > y) { 385 swap(x, y); 386 } 387 return z - x; 388 } 389 390 int main() { 391 ios::sync_with_stdio(0), cin.tie(0); 392 cin >> t; 393 while (t--) { 394 cin >> n; 395 for (int i = 1; i <= n; i++) { 396 cin >> a[i]; 397 } 398 399 ll ans = LINF; 400 for (int cyc = 0; cyc < 4; cyc++) { 401 dp[0] = 0; 402 dp[1] = LINF; 403 for (int i = 2; i <= n; i++) { 404 dp[i] = dp[i - 2] + cost(a[i - 1], a[i]); 405 if (i >= 3) { 406 dp[i] = 407 min(dp[i], dp[i - 3] + cost(a[i - 2], a[i - 1], a[i])); 408 } 409 } 410 ans = min(ans, dp[n]); 411 412 // cyclic shift anti-clockwise 413 for (int i = 2; i <= n; i++) { 414 swap(a[i], a[i - 1]); 415 } 416 } 417 418 cout << ans << '\n'; 419 } 420 return 0; 421 } 422 ``` 423 424 **Code (Pypy3.10, Little_Sheep_Yawn)** 425 426 ``` 427 import sys 428 input = lambda: sys.stdin.readline().strip() 429 430 t = int(input()) 431 outs = [] 432 fmin = lambda x, y: x if x < y else y 433 434 inf = 10 ** 15 435 for _ in range(t): 436 n = int(input()) 437 nums = list(map(int, input().split())) 438 439 ans = inf 440 441 for _ in range(3): 442 nums = nums[-1:] + nums[:-1] 443 dp = [inf] * (n + 1) 444 dp[0] = 0 445 446 for i in range(2, n + 1): 447 dp[i] = fmin(dp[i - 2] + max(nums[i-2:i]) - min(nums[i-2:i]), 448 dp[i - 3] + max(nums[i-3:i]) - min(nums[i-3:i]) if i >= 3 else inf) 449 450 ans = fmin(ans, dp[n]) 451 452 outs.append(ans) 453 454 print('\n'.join(map(str, outs))) 455 ``` 456 457 ### [2153E - Zero Trailing Factorial](/contest/2153/problem/E "Codeforces Round 1057 (Div. 2)") 458 459 **Hint 1** 460 461 Why is the answer always smaller than $10^{100}$ ? 462 463 **Hint 2** 464 465 There are only a few $k$-s that are worth choosing. 466 467 **Hint 3** 468 469 $f_m(x, n)$ is equal to $0$ for a lot of the $x$. 470 471 **Solution** 472 473 Let $p_0$ be the largest prime that is not greater than $n$. Then, $f_m(x, n) = 0$ for all $x \lt p_0$. 474 475 **Proof** 476 477 $v_{p_0}(x!) = 0$ for all $x \lt p_0$, and $v_{p_0}(n!) \gt 0$. Hence, $w_{p_0}(x, n) = \min(v_{p_0}(x!), v_{p_0}(n!)) = 0$. 478 479 Let $\mathrm{PrimeGap}(M)$ be the maximum difference between a number $x\ (2\leq x\leq M)$ and the largest prime number no larger than it. We only need to compute $\mathrm{PrimeGap}(n) \le \mathrm{PrimeGap}(10^7) = 152$ values of $f_m(x, n)$. As this is reasonably small, we will now try to calculate the value of each $f_m(x, n)$ for all possible $x \ge p_0$. 480 481 First, we state a simple but useful lemma: for all $k\ge 2$, $v_k(a!) \le v_k(b!)$ if $a\le b$. 482 483 **Proof** 484 485 $a!$ divides $b!$ if $a\le b$. Hence, if $k^i$ divides $a!$, it also divides $b!$. 486 487 To find out some more about $w_k(a,b)$, let's factor $k$ as $k=p_1^{v_1}p_2^{v_2}\ldots p_t^{v_t}$ where $p_1,p_2,\ldots,p_t$ are disctinct primes and $v_1,v_2,\ldots,v_t$ are positive integers. 488 489 Then, $w_k(a,b)\geq\min\limits_i w_{p_i^{v_i}}(a,b)$. 490 491 **Proof** 492 493 Without loss of generality, let $a\le b$. Consider the array $c=[v_{p_1^{v_1}}(a!),v_{p_2^{v_2}}(a!),\ldots,v_{p_t^{v_t}}(a!)]$, $d=[v_{p_1^{v_1}}(b!),v_{p_2^{v_2}}(b!),\ldots,v_{p_t^{v_t}}(b!)]$. Then $c_i\leq d_i$, for all $1\leq i\leq n$, since $v_{p_i^{v_i}}(a!)\leq v_{p_i^{v_i}}(b!)$ from the earlier lemma. 494 495 By definition, $v_k(a!) = \min(c)$, $v_k(b!) = \min(d)$, and 496 497 $w_k(a, b) = \begin{cases}10^{100} & \text{if } \min(c) = \min(d)\\ \min(c) &\text{otherwise}\end{cases}$ 498 499 (the second case is due to the lemma $v_k(a!)\le v_k(b!)$). 500 501 * If $v_k(a!) = v_k(b!)$, then $w_k(a,b)=10^{100}$. The inequality already holds. 502 * Otherwise, $v_k(a!) \neq v_k(b!)$, i.e., $\min(c)\neq\min(d)$. Since $c_i\leq d_i$ for all $i$, $\min(c) \lt \min(d)$. Let $i'$ be the index such that $c_i' = \min(c)$. Then, $c_{i'} = \min(c) \lt \min(d) \le d_{i'}$. Hence, $w_{p_{i'}^{v_i'}}(a, b) = c_{i'} = w_k(a, b)$. 503 504 Since $f_m(a, b)$ considers the minimum of $w_k(a, b)$ over all $2\le k\le m$, we only need to consider $k$ that are primes, or powers of primes. Formally, we only need to consider integers of the form $p^v$ where $p$ is a prime number and $v$ is a positive integer. 505 506 Furthermore, we only need to consider numbers of the form $p^v$ where $p$ is a prime number and $p$ divides at least one of the numbers in $[p_0, n]$. 507 508 **Proof** 509 510 For each $x$ in $[p_0,n]$, $x!=(p_0-1)!p_0(p_0+1)\ldots x$, which means $v_p(x!)=v_p((p_0-1)!)$. So it always holds that $v_p(x!)=v_p(n!)$, which also implies that $v_{p^k}(x!)=v_{p^k}(n!)$. 511 512 There are $\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n)$ primes $p$ that divide at least one of the numbers in $[p_0, n]$. We can calculate the value of $v_p(x!)$ and $v_p(n!)$ in $\mathcal{O}(\log_2 n)$ using the given formula. For each prime $p$, there are at most $\mathcal{O}(\log_2 m)$ prime powers $p^v \le m$, and $v_{p^k}(x!)$ and $v_{p^k}(n!)$ can both be calculated in $\mathcal{O}(1)$ time after computing $v_p(x!)$ and $v_p(n!)$ in the previous step. Hence, a single $f_m(x, n)$ can be computed in $\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n(\log_2 n + \log_2 m))$ time. 513 514 The total time complexity if $\mathcal{O}(t\cdot \mathrm{PrimeGap}(n)^2\log_2 n(\log_2 n + \log_2 m))$. Even though this seems very big, the constant is very small, so it passess comfortably. 515 516 **Code (C++, maomao90)** 517 518 ``` 519 #include <bits/stdc++.h> 520 using namespace std; 521 522 using ll = long long; 523 524 const int MAXN = 10000005; 525 const int INF = 1000000005; 526 527 bool is_prime[MAXN]; 528 529 inline int calc_v(int p, int x) { 530 int res = 0; 531 ll pw_p = p; 532 while (pw_p <= x) { 533 res += x / pw_p; 534 pw_p *= p; 535 } 536 return res; 537 } 538 539 int t; 540 int n, m; 541 vector<int> small_primes; 542 543 int main() { 544 #ifndef DEBUG 545 ios::sync_with_stdio(0), cin.tie(0); 546 #endif 547 for (int i = 2; i < MAXN; i++) { 548 is_prime[i] = true; 549 } 550 for (int p = 2; (ll)p * p < MAXN; p++) { 551 if (!is_prime[p]) { 552 continue; 553 } 554 small_primes.push_back(p); 555 for (int i = p * p; i < MAXN; i += p) { 556 is_prime[i] = false; 557 } 558 } 559 560 cin >> t; 561 while (t--) { 562 cin >> n >> m; 563 564 // find largest prime q <= n. Requires at most 142 iterations (due to 565 // prime gap) 566 int q = n; 567 while (!is_prime[q]) { 568 q--; 569 } 570 571 // precompute the useful big primes 572 vector<int> useful_p; 573 for (int f = 1; (ll)f * f <= n; f++) { 574 // p_bnd is the largest possible value such that floor(n / p_bnd) = 575 // f n / p_bnd >= f p_bnd <= n / f 576 int p_bnd = n / f; 577 int p = p_bnd; 578 while (!is_prime[p]) { 579 p--; 580 } 581 useful_p.push_back(p); 582 } 583 584 ll ans = 0; 585 // for all x < q, f_m(x, n) = 0. try all x >= q 586 for (int x = q; x < n; x++) { 587 int res = INF; 588 589 for (int p : useful_p) { 590 int vx = calc_v(p, x), vn = calc_v(p, n); 591 if (vx != vn) { 592 res = min(res, vx); 593 } 594 } 595 596 for (int p : small_primes) { 597 if ((ll)p * p > m) { 598 break; 599 } 600 601 int base_vx = calc_v(p, x), base_vn = calc_v(p, n); 602 for (ll exp = 1, pw_p = p; pw_p <= m; exp++, pw_p *= p) { 603 int vx = base_vx / exp, vn = base_vn / exp; 604 if (vx != vn) { 605 res = min(res, vx); 606 } 607 } 608 } 609 610 ans += res; 611 } 612 613 cout << ans << '\n'; 614 } 615 return 0; 616 } 617 ``` 618 619 **Code (Pypy3.10, Little_Sheep_Yawn)** 620 621 ``` 622 import sys 623 input = lambda: sys.stdin.readline().strip() 624 625 M = 10 ** 7 626 pr = [1] * (M + 1) 627 628 for i in range(2, M + 1): 629 if pr[i] == 1: 630 for j in range(i, M + 1, i): 631 pr[j] = i 632 633 t = int(input()) 634 outs = [] 635 636 fmin = lambda x, y: x if x < y else y 637 638 inf = 10 ** 9 639 640 for _ in range(t): 641 n, m = map(int(input().split())) 642 643 vis = set() 644 645 for i in range(n, 0, -1): 646 x = i 647 while x > 1: 648 vis.add(pr[x]) 649 x //= pr[x] 650 651 if pr[i] == i: break 652 653 ans = 0 654 655 def f(val, p): 656 c = 0 657 while val: 658 val //= p 659 c += val 660 return c 661 662 for i in range(n - 1, 0, -1): 663 res = inf 664 665 for v in vis: 666 cur = v 667 c = 1 668 669 v1 = f(i, v) 670 v2 = f(n, v) 671 672 while cur <= m: 673 674 if v1 // c != v2 // c: 675 res = fmin(res, v1 // c) 676 677 cur *= v 678 c += 1 679 680 ans += res 681 682 if pr[i] == i: break 683 684 outs.append(ans) 685 686 print('\n'.join(map(str, outs))) 687 ``` 688 689 ### [2153F - Odd Queries on Odd Array](/contest/2153/problem/F "Codeforces Round 1057 (Div. 2)") 690 691 **Hint 1** 692 693 What does the condition "there do not exist four indices $1\leq i\lt j\lt k\lt l\leq m$ such that $b_i\neq b_j$, $b_i=b_k$ and $b_j=b_l$." reminds you of? 694 695 **Hint 2** 696 697 You can construct a tree based on the array. How can you do so? 698 699 **Solution** 700 701 The strange condition given by the problem is that there are no subsequences in the form of $[x,y,x,y]\ (x\neq y)$. 702 703 Let us construct a tree such that its DFS order $^\dagger$ is equal to $a$. We can build the tree as follows: 704 705 * Initialize a stack containing a vertex $0$. 706 * Iterate over the array $a$ from index $i = 1$ to $i = n$. 707 * For each element $a[i]$: 708 + Add an edge between the vertex on top of the stack and vertex $i$. Assign vertex $i$ the value $a[i]$. 709 + If this is the first occurrence of $a[i]$, push $i$ onto the stack. 710 + If this is the last occurrence of $a[i]$, pop the top element from the stack (even if you have just pushed it). 711 712 Only the first and last occurrence of each value affects the stack. It can be proven that at the last occurence of each value, the vertex being popped from the stack will have the same value as the value of the processed vertex. This is because all elements in between the first and last occurrence of a value $x$ must be strictly contained in the range (due to the property of a cute array). Hence, all vertices that are pushed into the stack after the first occurrence of $x$ will be popped out before the last occurrence of $x$. 713 714 Due to the property of a cute array, the set of vertices with equal values forms a single connected component in the tre 715 716 **Proof** 717 718 Suppose that the set of vertices with equal values do not form a single connected component. Let $k$ be the value that do not form a single connected component, and let $u$ be the first occurrence of $a[u] = k$. Let $v$ be a vertex that is not connected to $u$, i.e., there exists a vertex $w$ on the simple path between $u$ and $v$ such that $a[w] \neq a[u]$. 719 720 Vertex $u$ has to be an ancestor of vertex $v$. This is because vertex $u$ will be pushed into the stack, and will remain in the stack until the last occurrence of $a[u]$, so $u$ will still be in the stack when $v$ is being processed. 721 722 Let $w$ be a vertex on the simple path between $u$ and $v$ such that $a[w] \neq a[u]$. $w$ is also an ancestor of $v$ since $u$ is an ancestor of $v$. $w$ has to be the first occurrence of $a[w]$ (for it to be pushed into the stack), and the last occurrence of $a[w]$ has to be after $v$ (otherwise it would be popped from the stack before $v$). This means that $[a[u], a[w], a[v], a[w]]$ exists as a subsequence of array $a$, which contradicts the condition of a cute array as $a[u] = a[v]$. 723 724 Since there can only be one vertex in the stack for each value, all vertices of the same value have the same parent. 725 726 To answer the queries, we decompose the range $l$ to $r$ into three parts by considering the lowest common ancestor (LCA) of vertex $l$ and vertex $r$: 727 728 * From $l$ to LCA: 729 + If $l$ has the same value as LCA, you can leave it to the second part. 730 + Otherwise, let $l'$ be the child vertex of LCA which is an ancestor of $l$, and $\text{last}_{l'}$ be the vertex with the largest index in the subtree of $l'$. The values that appear in the subtree of $l'$ never occur in other parts of the tree. Hence, the answer for the subarray $a_{l\ldots \text{last}_{l'}}$ is equals to the answer for the suffix $a_{l\ldots n}$ minus the answer for the suffix $a_{\text{last}_{l'} + 1\ldots n}$. By precomputing the answer for each suffix of the entire array $a$, we can find the answer for subarray $a_{l\ldots \text{last}_{l'}}$ in $\mathcal{O}(1)$ time. 731 * At LCA: 732 + Let $r'$ be the child vertex of the LCA which is an ancestor of $r$. We want to compute the answer for the subarray $a_{\text{last}_{l'} + 1\ldots r'-1}$. 733 + This can be done by considering the children of the LCA between $l'$ and $r'$, then summing up the answer for the subtrees of those children. 734 - For subtrees that are a single vertex, they have the same value as the LCA. We can count the occurrence of the value between vertex $l'$ and $r'$ in $\mathcal{O}(1)$ time after precomputing prefix sums. 735 - For other subtrees, the answer for their corresponding subarray is independent of the rest of the array. Hence, we can precompute the answer for the subtree of each vertex with a simple DFS. Then, we can sum up the answer for the subtrees of all children between $l'$ and $r'$ using perfix sums. 736 * From LCA to $r$: 737 + This is handled in the same way as the first part, except that we need to precompute the answer for each prefix of the entire array instead of the suffix. 738 739 The time complexity is $\mathcal{O}(n+q\log n)$. 740 741 $^\dagger$ The DFS order of a tree is found by calling the following `dfs` function on the tree. 742 743 ``` 744 dfs_order = [] 745 746 def dfs(v): 747 dfs_order.append(v) 748 # children[v] is the set of children of vertex v 749 for child in children[v]: 750 dfs(child) 751 752 dfs(0) 753 ``` 754 755 **Code (Pypy 3.10, Little_Sheep_Yawn)** 756 757 ``` 758 import sys 759 import bisect 760 input = lambda: sys.stdin.readline().strip() 761 762 t = int(input()) 763 outs = [] 764 765 fmax = lambda x, y: x if x > y else y 766 767 for _ in range(t): 768 n, q = map(int, input().split()) 769 nums = [0] + list(map(int, input().split())) 770 771 first_pos = [0] * (n + 1) 772 last_pos = [0] * (n + 1) 773 774 for i in range(n + 1): 775 last_pos[nums[i]] = i 776 777 for i in range(n, -1, -1): 778 first_pos[nums[i]] = i 779 780 path = [[] for _ in range(n + 1)] 781 nth_parent = [[-1] * (n + 1) for _ in range(20)] 782 depth = [0] * (n + 1) 783 784 stk = [0] 785 786 for i in range(1, n + 1): 787 path[stk[-1]].append(i) 788 nth_parent[0][i] = stk[-1] 789 depth[i] = depth[stk[-1]] + 1 790 791 if first_pos[nums[i]] == i: 792 stk.append(i) 793 if last_pos[nums[i]] == i: 794 stk.pop() 795 796 depth.append(-1) 797 798 for i in range(19): 799 for j in range(n + 1): 800 if nth_parent[i][j] != -1: 801 nth_parent[i + 1][j] = nth_parent[i][nth_parent[i][j]] 802 803 cnt = [0] * (n + 1) 804 cur = 0 805 806 pref_val = [0] * (n + 1) 807 808 for i in range(1, n + 1): 809 cur += -nums[i] if cnt[nums[i]] else nums[i] 810 cnt[nums[i]] ^= 1 811 pref_val[i] = cur 812 813 cnt = [0] * (n + 1) 814 cur = 0 815 816 suff_val = [0] * (n + 1) 817 818 for i in range(n, 0, -1): 819 cur += -nums[i] if cnt[nums[i]] else nums[i] 820 cnt[nums[i]] ^= 1 821 suff_val[i - 1] = cur 822 823 subtree_val = [0] * (n + 1) 824 subtree_max_idx = list(range(n + 1)) 825 826 for i in range(n, -1, -1): 827 if first_pos[nums[i]] == i: 828 c = 1 829 total = 0 830 831 for j in path[i]: 832 total += subtree_val[j] 833 if nums[j] == nums[i]: 834 c ^= 1 835 subtree_max_idx[i] = fmax(subtree_max_idx[i], subtree_max_idx[j]) 836 837 subtree_val[i] = total + c * nums[i] 838 839 accs = [[0] * (len(path[i]) + 2) if first_pos[nums[i]] == i else [] for i in range(n + 1)] 840 841 for i in range(n + 1): 842 if first_pos[nums[i]] == i: 843 total = 0 844 c = 1 845 accs[i][1] = total * 2 + c 846 847 for j in range(len(path[i])): 848 total += subtree_val[path[i][j]] 849 if nums[path[i][j]] == nums[i]: 850 c ^= 1 851 accs[i][j + 2] = total * 2 + c 852 853 def lca(u, v): 854 if depth[u] < depth[v]: 855 u, v = v, u 856 d = depth[u] - depth[v] 857 858 while d: 859 x = d & -d 860 bit = x.bit_length() - 1 861 u = nth_parent[bit][u] 862 d -= x 863 864 if u == v: return u 865 866 for i in range(19, -1, -1): 867 if nth_parent[i][u] != nth_parent[i][v]: 868 u = nth_parent[i][u] 869 v = nth_parent[i][v] 870 871 return nth_parent[0][u] 872 873 last = 0 874 ans = [0] * q 875 876 for idx in range(q): 877 l, r = map(int, input().split()) 878 l = (l + last - 1) % n + 1 879 r = (r + last - 1) % n + 1 880 881 if l > r: l, r = r, l 882 ancestor = lca(l, r) 883 884 if l == r: 885 last = nums[l] 886 else: 887 last = 0 888 889 if l == ancestor and first_pos[nums[l]] == l: 890 pl = 0 891 elif nth_parent[0][l] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[l]] != l: 892 pl = bisect.bisect_left(path[ancestor], l) + 1 893 else: 894 cl = l 895 for i in range(19, -1, -1): 896 if depth[nth_parent[i][cl]] > depth[ancestor]: 897 cl = nth_parent[i][cl] 898 last += suff_val[l - 1] - suff_val[subtree_max_idx[cl]] 899 pl = bisect.bisect_left(path[ancestor], cl) + 2 900 901 if r == ancestor and first_pos[nums[r]] == r: 902 pr = 0 903 elif nth_parent[0][r] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[r]] != r: 904 pr = bisect.bisect_left(path[ancestor], r) + 1 905 else: 906 cr = r 907 for i in range(19, -1, -1): 908 if depth[nth_parent[i][cr]] > depth[ancestor]: 909 cr = nth_parent[i][cr] 910 last += pref_val[r] - pref_val[cr - 1] 911 pr = bisect.bisect_left(path[ancestor], cr) 912 913 xl = accs[ancestor][pl] 914 xr = accs[ancestor][pr + 1] 915 916 vl, cl = divmod(xl, 2) 917 vr, cr = divmod(xr, 2) 918 919 last += vr - vl + (cl ^ cr) * nums[ancestor] 920 921 ans[idx] = last 922 923 outs.append(' '.join(map(str, ans))) 924 925 print('\n'.join(outs)) 926 ``` 927 928 **Code (C++, maomao90, slightly different)** 929 930 ``` 931 #include <bits/stdc++.h> 932 using namespace std; 933 934 using ll = long long; 935 936 namespace solution { 937 938 const int MAXL = 21; 939 const int MAXN = 1000005; 940 941 int n, q; 942 int a[MAXN]; 943 vector<int> occ[MAXN]; 944 ll pfx[MAXN], sfx[MAXN]; 945 ll sm_pfx[MAXN], sm_sfx[MAXN]; 946 947 inline bool is_first_occ(int i) { return occ[a[i]][0] == i; } 948 inline bool is_last_occ(int i) { return occ[a[i]].back() == i; } 949 // returns minimum j >= p such that a[j] == x, or n + 1 if does not exist 950 inline auto nxt_occ(int p, int x) { 951 return lower_bound(occ[x].begin(), occ[x].end(), p); 952 } 953 954 int p[MAXL][MAXN]; 955 vector<int> adj[MAXN]; 956 inline void add_edge(int u, int v) { 957 p[0][v] = u; 958 adj[u].push_back(v); 959 } 960 961 int lvl[MAXN]; 962 void dfs(int u) { 963 for (int l = 1; l < MAXL; l++) { 964 p[l][u] = p[l - 1][p[l - 1][u]]; 965 } 966 if (u) { 967 sm_pfx[u] += pfx[u]; 968 auto ptr = nxt_occ(u + 1, a[u]); 969 sm_sfx[u] += ptr == occ[a[u]].end() ? 0 : sfx[*ptr]; 970 } 971 for (int v : adj[u]) { 972 lvl[v] = lvl[u] + 1; 973 sm_pfx[v] = sm_pfx[u]; 974 sm_sfx[v] = sm_sfx[u]; 975 dfs(v); 976 } 977 } 978 979 tuple<int, int, int> get_lca(int a, int b) { 980 bool swp = false; 981 if (lvl[a] < lvl[b]) { 982 swap(a, b); 983 swp = true; 984 } 985 for (int l = MAXL - 1; l >= 0; l--) { 986 if (lvl[p[l][a]] >= lvl[b]) { 987 a = p[l][a]; 988 } 989 } 990 if (a == b) { 991 return {a, -1, -1}; 992 } 993 if (swp) { 994 swap(a, b); 995 } 996 for (int l = MAXL - 1; l >= 0; l--) { 997 if (p[l][a] != p[l][b]) { 998 a = p[l][a]; 999 b = p[l][b]; 1000 } 1001 } 1002 return {p[0][a], a, b}; 1003 } 1004 1005 ll solve_same_layer(int l, int r) { 1006 assert(p[0][l] == p[0][r]); 1007 ll res = 1008 (pfx[r] - 1009 ((nxt_occ(r + 1, a[l]) - occ[a[l]].begin()) % 2 == 1 ? a[l] : 0)) - 1010 (pfx[l] - 1011 ((nxt_occ(l, a[l]) - occ[a[l]].begin() + 1) % 2 == 1 ? a[l] : 0)); 1012 if ((nxt_occ(r + 1, a[l]) - nxt_occ(l, a[l])) % 2 == 1) { 1013 res += a[l]; 1014 } 1015 return res; 1016 } 1017 1018 void precompute() { 1019 for (int i = 0; i <= n; i++) { 1020 occ[i].clear(); 1021 adj[i].clear(); 1022 pfx[i] = sfx[i] = sm_pfx[i] = sm_sfx[i] = 0; 1023 } 1024 for (int i = 1; i <= n; i++) { 1025 occ[a[i]].push_back(i); 1026 } 1027 vector<int> stk; 1028 stk.push_back(0); 1029 for (int i = 1; i <= n; i++) { 1030 if (!is_first_occ(i)) { 1031 assert(!stk.empty() && a[stk.back()] == a[i]); 1032 stk.pop_back(); 1033 } 1034 assert(!stk.empty()); 1035 add_edge(stk.back(), i); 1036 if (!is_last_occ(i)) { 1037 stk.push_back(i); 1038 } 1039 } 1040 1041 for (int u = n; u >= 0; u--) { 1042 { 1043 ll prv = 0; 1044 for (int i = 0; i < (int)adj[u].size(); i++) { 1045 int v = adj[u][i]; 1046 auto ptr = nxt_occ(v, a[v]); 1047 pfx[v] = 1048 prv + ((ptr - occ[a[v]].begin() + 1) % 2 == 1 ? a[v] : 0); 1049 if (!adj[v].empty()) { 1050 prv += pfx[adj[v].back()]; 1051 } 1052 if (is_last_occ(v)) { 1053 prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0; 1054 } 1055 } 1056 } 1057 { 1058 ll prv = 0; 1059 for (int i = (int)adj[u].size() - 1; i >= 0; i--) { 1060 int v = adj[u][i]; 1061 auto ptr = nxt_occ(v, a[v]); 1062 if (!adj[v].empty()) { 1063 prv += sfx[adj[v][0]]; 1064 } 1065 sfx[v] = prv + ((occ[a[v]].end() - ptr) % 2 == 1 ? a[v] : 0); 1066 if (is_first_occ(v)) { 1067 prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0; 1068 } 1069 } 1070 } 1071 } 1072 1073 dfs(0); 1074 } 1075 1076 void init(int _n, int _q, vector<int> _a) { 1077 n = _n; 1078 q = _q; 1079 for (int i = 1; i <= n; i++) { 1080 a[i] = _a[i - 1]; 1081 } 1082 precompute(); 1083 } 1084 1085 ll query(int l, int r) { 1086 if (l == r) { 1087 return a[l]; 1088 } 1089 auto [lca, lc, rc] = get_lca(l, r); 1090 assert(lca != r); 1091 if (lca == l) { 1092 ll ans = sm_pfx[r] - sm_pfx[l] + a[l]; 1093 return ans; 1094 } else if (lc == l) { 1095 ll ans = sm_pfx[r] - sm_pfx[rc]; 1096 ans += solve_same_layer(l, rc); 1097 return ans; 1098 } else { 1099 ll ans = sfx[l] + sm_sfx[p[0][l]] - sm_sfx[lc] + sm_pfx[r] - sm_pfx[rc]; 1100 ans += solve_same_layer(*nxt_occ(lc + 1, a[lc]), rc); 1101 return ans; 1102 } 1103 } 1104 1105 } // namespace solution 1106 1107 int main() { 1108 ios::sync_with_stdio(0), cin.tie(0); 1109 int t; 1110 cin >> t; 1111 while (t--) { 1112 int n, q; 1113 cin >> n >> q; 1114 vector<int> a(n); 1115 for (int i = 0; i < n; i++) { 1116 cin >> a[i]; 1117 } 1118 1119 solution::init(n, q, a); 1120 ll prv_ans = 0; 1121 while (q--) { 1122 int l, r; 1123 cin >> l >> r; 1124 auto decode = [&](int x) { return (x - 1 + prv_ans) % n + 1; }; 1125 l = decode(l); 1126 r = decode(r); 1127 if (l > r) { 1128 swap(l, r); 1129 } 1130 ll ans = solution::query(l, r); 1131 cout << ans << ' '; 1132 prv_ans = ans; 1133 } 1134 cout << '\n'; 1135 } 1136 return 0; 1137 } 1138 ```