1827.md (36028B)
1 Source: https://codeforces.com/blog/entry/116109 2 3 ## [1828A - Divisible Array](/contest/1828/problem/A "Codeforces Round 873 (Div. 2)") 4 5 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 6 Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235") 7 8 **Hint 1** 9 10 Remember the sum of the first $n$ positive integers? 11 12 **Hint 2** 13 14 Every positive integer is divisible by $1$. 15 16 **Solution** 17 18 Consider the array $a = \left[1, 2, \ldots, n\right]$ that satisfies the second condition. It has the sum of $1 + 2 + \dots + n = \frac{n(n+1)}{2}$. 19 20 One solution is to notice that if we double every element $(a=\left[2, 4, 6, \ldots, 2n\right])$, the sum becomes $\frac{n(n+1)}{2} \times 2 = n(n + 1)$, which is divisible by $n$. 21 22 Another solution is to increase the value of $a_1$ until the sum becomes divisible by $n$. This works because every integer is divisible by $1$, and we only need to increase $a_1$ by at most $n$. 23 24 Time complexity: $\mathcal{O}(n)$ 25 26 **Implementation 1** 27 28 ``` 29 #include <bits/stdc++.h> 30 31 using namespace std; 32 33 int main() { 34 35 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 36 37 int t; 38 cin >> t; 39 while (t--) { 40 int n; 41 cin >> n; 42 for (int i = 1; i <= n; i++) cout << i * 2 << " "; 43 cout << "\n"; 44 } 45 } 46 ``` 47 48 **Implementation 2** 49 50 ``` 51 #include<bits/stdc++.h> 52 using namespace std; 53 typedef long long ll; 54 #define fi first 55 #define se second 56 const int N=2e6+1; 57 const ll mod=998244353; 58 ll n,m; 59 ll a[N],b[N]; 60 void solve(){ 61 cin >> n; 62 ll s=0; 63 for(int i=n; i>=2 ;i--){ 64 a[i]=i; 65 s=(s+i)%n; 66 } 67 a[1]=n-s; 68 for(int i=1; i<=n ;i++) cout << a[i] << ' '; 69 cout << '\n'; 70 } 71 int main(){ 72 ios::sync_with_stdio(false);cin.tie(0); 73 int t;cin >> t; 74 while(t--){ 75 solve(); 76 } 77 } 78 ``` 79 80 ## [1828B - Permutation Swap](/contest/1828/problem/B "Codeforces Round 873 (Div. 2)") 81 82 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 83 Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235") 84 85 **Hint 1** 86 87 In order to move $p_i$ to its right position, what does the value of $k$ have to satisfy? 88 89 **Solution** 90 91 In order to move $p_i$ to position $i$, it is easy to see that $|p_i - i|$ has to be divisible by $k$. 92 93 So, $|p_1 - 1|, |p_2 - 2|, \ldots, |p_n - n|$ has to be all divisible by $k$. The largest possible value of $k$ turns out to be the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $|p_1 - 1|, |p_2 - 2|, \ldots, |p_n - n|$. 94 95 Time complexity: $\mathcal{O}(n + \log{n})$ 96 97 **Implementation** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 signed main() { 105 106 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 107 108 int t; 109 cin >> t; 110 while (t--) { 111 int n, res = 0; 112 cin >> n; 113 for (int i = 1; i <= n; i++) { 114 int x; cin >> x; 115 res = __gcd(res, abs(x - i)); 116 } 117 cout << res << "\n"; 118 } 119 120 } 121 ``` 122 123 ## [1827A - Counting Orders](/contest/1827/problem/A "Codeforces Round 873 (Div. 1)") 124 125 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235") 126 Preparation: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 127 128 **Hint 1** 129 130 Sort the array $b$, and fix the values from $a_n$ to $a_1$. 131 132 **Solution** 133 134 First, we can sort the array $b$, as it does not change the answer. 135 136 Let's try to choose the values of $a$ from $a_n$ to $a_1$. How many ways are there to choose the value of $a_i$? 137 138 The new $a_i$ must satisfies $a_i \gt b_i$. But some of the candidates are already chosen as $a_j$ for some $j \gt i$. However, since $a_j \gt b_j \ge b_i$, we know that there are exactly $(n - i)$ candidates already chosen previously by all values of $j \gt i$. So, there are (number of $k$ such that $a_k \gt b_i$) $- (n - i)$ ways to choose the value of $a_i$. 139 140 We can use two pointers or binary search to efficiently find the (number of $k$ such that $a_k \gt b_i$) for all $i$. 141 142 Time complexity: $\mathcal O(n \log n)$. 143 144 **Implementation** 145 146 ``` 147 #include <bits/stdc++.h> 148 using namespace std; 149 typedef long long ll; 150 const int MOD = 1e9 + 7; 151 152 struct testcase{ 153 testcase(){ 154 int n; cin >> n; 155 vector<int> a(n); 156 for (int i=0; i<n; i++) cin >> a[i]; 157 sort(a.begin(), a.end()); 158 vector<int> b(n); 159 for (int i=0; i<n; i++) cin >> b[i]; 160 sort(b.begin(), b.end(), greater<>()); 161 ll result = 1; 162 for (int i=0; i<n; i++){ 163 int geq_count = a.size() - (upper_bound(a.begin(), a.end(), b[i]) - a.begin()); 164 result = result * max(geq_count - i, 0) % MOD; 165 } 166 cout << result << "\n"; 167 } 168 }; 169 170 signed main(){ 171 cin.tie(0)->sync_with_stdio(0); 172 int t; cin >> t; 173 while (t--) testcase(); 174 } 175 ``` 176 177 ## [1827B2 - Range Sorting (Hard Version)](/contest/1827/problem/B2 "Codeforces Round 873 (Div. 1)") 178 179 Idea: [lanhf](/profile/lanhf "Master lanhf") 180 Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235") 181 182 **Hint 1** 183 184 What is the minimum cost to sort just one subarray? 185 186 **Hint 2** 187 188 What happens when two operations intersect each other? 189 190 **Hint 3** 191 192 When can we sort two adjacency ranges independently? 193 194 **Hint 4** 195 196 Try to calculate the contribution of each position. 197 198 **Solution** 199 200 Let $a[l..r]$ denotes the subarray $a_l,a_{l+1},\ldots,a_r$. 201 202 **Observation 1**: In an optimal sequence of operations for one subarray, there will be no two operations that intersect each other. In other words, a subarray will be divided into non-overlapping subarrays, and we will apply a range-sort operation to each subarray. 203 204 *Proof*: Suppose there are two operations $[l_1,r_1]$ and $[l_2,r_2]$ that intersect each other, we can replace them with one operation $[\min(l_1,l_2),\max(r_1,r_2)]$ which does not increase the cost. 205 206 **Observation 2**: Consider $k$ positions $l\le i_1 \lt i_2 \lt \ldots \lt i_k \lt r$, then we can sort subarrays $a[l..i_1],$ $a[i_1+1..i_2],$ $\ldots,$ $a[i_k+1..r]$ independently iff $\max(a[l..i_x]) \lt \min(a[i_x+1..r])$ for all $1\le x\le k$. 207 208 *Proof*: The obvious necessary and sufficient condition required to sort subarrays $a[l..i_1],$ $a[i_1+1..i_2],$ $\ldots,$ $a[i_k+1..r]$ independently is $\max(a[i_{x-1}+1..i_x]) \lt \min(a[i_x+1..i_{x+1}])$ for all $1\le x\le k$, here we denote $x_0=l-1$ and $x_{k+1}=r$. It is not hard to prove that this condition is equal to the one stated above. 209 210 With these observations, we can conclude that the answer for a subarray $a[l..r]$ equals the $r-l$ minus the number of positions $k$ such that $l\le k\lt r$ and $\max(a[l..k]) \lt \min(a[k+1..r])$ $(*)$. Let us analyze how to calculate the sum of this value over all possible $l$ and $r$. 211 212 Consider a position $i$ ($1\le i\le n$), let's count how many triplets $(l, k, r)$ satisfy $(*)$ and $min(a[k+1..r]) = a_i$. It means that $k$ must be the closest position to the left of $i$ satisfying $a_k \lt a_i$. Denotes $x$ as the closest position to the left of $k$ such that $a_x \gt a_i$, and $y$ as the closest position to the right of $i$ such that $a_y \lt a_i$. 213 214 We can see that a triplet $(l, k, r)$ with $x \lt l\le k$ and $i\le r \lt y$ will match our condition. In other words, we will add to the answer $(k - x) \cdot (y - i)$. 215 216 In the easy version, we can find such values of $x, k, y$ for each $i$ in $\mathcal{O}(n)$ and end up with a total complexity of $O(n^2)$. We can further optimize the algorithm by using sparse table and binary lifting and achieve a time complexity of $\mathcal{O}(n \log{n})$, which is enough to solve the hard version. 217 218 There is an $\mathcal{O}(n)$ solution described [here](https://codeforces.com/blog/entry/116109?#comment-1029986). 219 220 **Implementation 1** 221 222 ``` 223 #include <bits/stdc++.h> 224 225 using namespace std; 226 227 const int N = 500005; 228 const int LOG = 19; 229 230 int a[N], r[N], rmq[LOG][N]; 231 232 void solve() { 233 int n; cin >> n; 234 long long res = 0; 235 vector<int> s; 236 a[0] = a[n + 1] = 0; 237 for (int i = 1; i <= n; i++) { 238 cin >> a[i]; 239 rmq[0][i] = a[i]; 240 res += 1ll * i * (i - 1) / 2; 241 } 242 s.push_back(n + 1); 243 for (int i = n; i > 0; i--) { 244 while (a[s.back()] > a[i]) 245 s.pop_back(); 246 r[i] = s.back(); 247 s.push_back(i); 248 } 249 for (int k = 1; k < LOG; k++) 250 for (int i = (1 << k); i <= n; i++) 251 rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i - (1 << (k - 1))]); 252 s.clear(); 253 s.push_back(0); 254 for (int i = 1; i <= n; i++) { 255 while (a[s.back()] > a[i]) 256 s.pop_back(); 257 int j = s.back(); 258 for (int k = LOG - 1; k >= 0; k--) 259 if (j >= (1 << k) && rmq[k][j] < a[i]) 260 j -= 1 << k; 261 res -= 1ll * (r[i] - i) * (s.back() - j); 262 s.push_back(i); 263 } 264 cout << res << '\n'; 265 } 266 267 int main() { 268 cin.tie(0)->sync_with_stdio(0); 269 int t; cin >> t; 270 while (t--) solve(); 271 } 272 ``` 273 274 **Implementation 2** 275 276 ``` 277 #include <bits/stdc++.h> 278 using namespace std; 279 280 const int N = 3e5 + 5; 281 282 int n; 283 int a[N]; 284 285 pair <int, int> b[N]; 286 287 signed main(){ 288 ios_base::sync_with_stdio(0); 289 cin.tie(0); cout.tie(0); 290 int tests; cin >> tests; while (tests--){ 291 cin >> n; 292 for (int i = 1; i <= n; i++){ 293 cin >> a[i]; 294 } 295 296 for (int i = 1; i <= n; i++){ 297 b[i] = make_pair(a[i], i); 298 } 299 sort(b + 1, b + n + 1); 300 301 set <int> sttlo = {0, n + 1}, stthi = {0, n + 1}; 302 for (int i = 1; i <= n; i++){ 303 stthi.emplace(i); 304 } 305 long long ans = 0; 306 for (int len = 1; len <= n; len++){ 307 ans += (long long)(len - 1) * (n - len + 1); 308 } 309 for (int i = 1; i <= n; i++){ 310 int idx = b[i].se; 311 stthi.erase(idx); sttlo.emplace(idx); 312 313 int x2 = *stthi.lower_bound(idx); 314 int x1 = *prev(stthi.lower_bound(idx)); 315 if (x2 == n + 1){ 316 continue; 317 } 318 int x3 = *sttlo.lower_bound(x2); 319 ans -= (long long)(idx - x1) * (x3 - x2); 320 } 321 cout << ans << endl; 322 } 323 } 324 ``` 325 326 **Bonus** 327 328 Solve the problem when the beauty of an array is (minimum time needed to sort)$^2$. 329 330 ## [1827C - Palindrome Partition](/contest/1827/problem/C "Codeforces Round 873 (Div. 1)") 331 332 Idea: [lanhf](/profile/lanhf "Master lanhf") 333 Preparation: [lanhf](/profile/lanhf "Master lanhf") 334 335 **Hint1** 336 337 Try to construct beautiful string greedily. 338 339 **Hint2** 340 341 What happens when we have two even palindromes share one of their endpoints? 342 343 **Solution** 344 345 For the simplicity of the solution, we will abbreviate even palindrome as evp. 346 347 **Lemma**: Consider a beautiful string $t$, we can find the **unique maximal** partition for it by greedily choosing the smallest possible evp in each step from the left. Here maximal means maximum number of parts. 348 349 *Proof*: Suppose $t[0..l)$ is smallest prefix which is an evp and $t[0..r)$ is the first part in the partition of $t$, here $t[l..r)$ mean substring $t_l t_{l+1}\ldots t_{r-1}$. We consider two cases: 350 351 * $2l\le r$: In this case, it is clear that $t[0..l)$, $t[l..r - l)$ and $t[r-l..r)$ are evps, so we can replace $t[0..r)$ with them. 352 353  354 355 * $2l \gt r$: In this case, due to the fact that $t[r-l..l)$ and $t[0..l)$ are evps, $t[0..2l-r)$ is also an evp, which contradicts to above assumption that $t[0..l)$ is the smallest. 356 357  358 359 We can use dynamic programming to solve this problem. Let $dp_i$ be the number of beautiful substrings starting at $i$. For all $i$ from $n-1$ to $0$, if there are such $next_i$ satisfying $s[i..next_i)$ is the smallest evp beginning at $i$, then $dp_i=dp_{next_i}+1$, otherwise $dp_i=0$. The answer will be the sum of $dp_i$ from $0$ to $n-1$. 360 361 To calculate the $next$ array, first, we use Manacher algorithm or hashing to find the maximum $pal_i$ satisfying $s[i-pal_i..i+pal_i)$ is an evp for each $i$. Then for all $0\le i \lt n$, $next_i=2j-i$ where $j$ is smallest position such that $i \lt j$ and $j-pal_j\le i$. The time complexity is $\mathcal{O}(n \log{n})$. 362 363 **Implementation** 364 365 ``` 366 #include <bits/stdc++.h> 367 368 using namespace std; 369 370 const int N = 500005; 371 const int LOG = 19; 372 373 int n, pal[N], rmq[LOG][N], cnt[N]; 374 string s; 375 376 int main() { 377 cin.tie(0)->sync_with_stdio(0); 378 int t; cin >> t; 379 while (t--) { 380 cin >> n >> s; 381 for (int i = 0, l = 0, r = 0; i < n; i++) { 382 pal[i] = i >= r ? 0 : min(pal[l + r - i], r - i); 383 while (i + pal[i] < n && i - pal[i] - 1 >= 0 384 && s[i + pal[i]] == s[i - pal[i] - 1]) pal[i]++; 385 if (i + pal[i] > r) { 386 l = i - pal[i]; r = i + pal[i]; 387 } 388 } 389 for (int i = 0; i < n; i++) 390 rmq[0][i] = i - pal[i]; 391 for (int k = 1; k < LOG; k++) 392 for (int i = 0; i + (1 << k) <= n; i++) 393 rmq[k][i] = min(rmq[k - 1][i], 394 rmq[k - 1][i + (1 << (k - 1))]); 395 for (int i = 1; i <= n; i++) 396 cnt[i] = 0; 397 for (int i = 0; i < n; i++) { 398 int j = i + 1; 399 for (int k = LOG - 1; k >= 0; k--) 400 if (j + (1 << k) <= n && rmq[k][j] > i) 401 j += 1 << k; 402 if (2 * j - i <= n) 403 cnt[2 * j - i] += cnt[i] + 1; 404 405 } 406 long long res = 0; 407 for (int i = 1; i <= n; i++) 408 res += cnt[i]; 409 cout << res << '\n'; 410 } 411 } 412 ``` 413 414 **Bonus** 415 416 Solve the problem in $\mathcal{O}(n)$. 417 418 ## [1827D - Two Centroids](/contest/1827/problem/D "Codeforces Round 873 (Div. 1)") 419 420 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235") 421 Preparation: [lanhf](/profile/lanhf "Master lanhf") 422 423 **Hint1** 424 425 Is the answer related to the centroid of the current tree? 426 427 **Hint2** 428 429 How much the centroid will move after one query? 430 431 **Solution** 432 433 **Observation**: The answer for the tree with $n$ vertices equals $n-2\cdot mx$ where $mx$ is the largest subtree among the centroid's children. 434 435 **Lemma**: After one query, the centroid will move at most one edge, and when the centroid move, the tree before the query already has two centroids. 436 437 *Proof*: 438 439  440 441 Suppose the tree before the query has $n$ vertices and the current centroid is $u$. Let $v_1, v_2,\ldots,v_k$ are the children of $u$ and the next query vertex $x$ is in subtree $v_1$. Clearly, the centroid is either $u$ or in the subtree $v_1$. Consider the latter case, because the size of subtree $v_1$ does not greater than $\lfloor \frac{n}{2}\rfloor$, the size of newly formed subtree including $u$ is greater or equal to $\lceil \frac{n}{2}\rceil$. Moving one or more edges away from $v_1$ will increase the size of this new subtree by one or more, and the vertex can not become centroid because $\lceil \frac{n}{2}\rceil+1 \gt \lfloor \frac{n+1}{2}\rfloor$. 442 443 The second part is easy to deduce from the above proof. 444 445 We will solve this problem offline. First, we compute the Euler tour of the final tree and use "range add query" data structures like Binary indexed tree (BIT) or Segment tree to maintain each subtree's size. We will maintain the size of the largest subtree among the centroid's children $mx$. In the case where the centroid does not move, we just update $mx$ with the size of the subtree including the newly added vertex, otherwise, we set $mx$ to $\lfloor \frac{n}{2}\rfloor$ due to the lemma. The time complexity is $\mathcal{O}(n \log{n})$. 446 447 **Implementation** 448 449 ``` 450 #include <bits/stdc++.h> 451 452 using namespace std; 453 454 const int N = 500005; 455 const int LOG = 19; 456 457 vector<int> adj[N]; 458 int tin[N], tout[N], timer; 459 int par[LOG][N], bit[N], dep[N]; 460 461 void dfs(int u) { 462 tin[u] = ++timer; 463 dep[u] = dep[par[0][u]] + 1; 464 for (int k = 1; k < LOG; k++) 465 par[k][u] = par[k - 1][par[k - 1][u]]; 466 for (int v : adj[u]) dfs(v); 467 tout[u] = timer; 468 } 469 470 void add(int u) { 471 for (int i = tin[u]; i < N; i += i & -i) 472 bit[i]++; 473 } 474 475 int get(int u) { 476 int res = 0; 477 for (int i = tout[u]; i > 0; i -= i & -i) 478 res += bit[i]; 479 for (int i = tin[u] - 1; i > 0; i -= i & -i) 480 res -= bit[i]; 481 return res; 482 } 483 484 int jump(int u, int d) { 485 for (int k = 0; k < LOG; k++) 486 if (d >> k & 1) u = par[k][u]; 487 return u; 488 } 489 490 bool cover(int u, int v) { 491 return tin[u] <= tin[v] && tin[v] <= tout[u]; 492 } 493 494 void solve() { 495 int n; cin >> n; 496 497 /// reset 498 timer = 0; 499 for (int i = 1; i <= n; i++) { 500 bit[i] = 0; adj[i].clear(); 501 } 502 503 for (int i = 2; i <= n; i++) { 504 cin >> par[0][i]; 505 adj[par[0][i]].push_back(i); 506 } 507 dfs(1); add(1); 508 int cen = 1, max_siz = 0; 509 for (int u = 2; u <= n; u++) { 510 add(u); 511 if (cover(cen, u)) { 512 int v = jump(u, dep[u] - dep[cen] - 1); 513 int siz = get(v); 514 if (siz >= (u + 1) / 2) { 515 cen = v; max_siz = u / 2; 516 } else max_siz = max(max_siz, siz); 517 } else { 518 int siz = get(cen); 519 if (siz < (u + 1) / 2) { 520 cen = par[0][cen]; max_siz = u / 2; 521 } else max_siz = max(max_siz, u - siz); 522 } 523 cout << u - 2 * max_siz << " \n"[u == n]; 524 } 525 } 526 527 int main() { 528 cin.tie(0)->sync_with_stdio(0); 529 int t; cin >> t; 530 while (t--) solve(); 531 } 532 ``` 533 534 **flowerletter :pensive:** 535 536  537 538 ## [1827E - Bus Routes](/contest/1827/problem/E "Codeforces Round 873 (Div. 1)") 539 540 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235") 541 Preparation: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 542 543 **Hint 1** 544 545 You do not need to consider all pairs of nodes, only some of them will do. 546 547 **Hint 2** 548 549 Find an equivalent condition of the statement. 550 551 **Hint 2.1** 552 553 Let $S(u)$ be the set of all nodes reachable by u using at most one route. Consider all $S(l)$ where $l$ is a leaf in the tree. 554 555 **Solution** 556 557 First, notice that for a pair of nodes $(u, v)$ such that $u$ is not a leaf, we can find a leaf $l$ such that path $(l, v)$ fully covers path $(u, v)$. Therefore, we only need to care about whether all pairs of leaves can reach each other using at most $2$ routes. 558 559 **Lemma** 560 561 The condition above is equivalent to: There exists a node $c$ such that $c$ can reach all leaves by using at most one route. 562 563 *Proof* 564 565 The necessity part is trivial, so let's prove the sufficiency part. 566 567 Let the leaves of the tree be $l_1, l_2, \ldots, l_m$. 568 569 Let $S(u)$ be the induced subgraph of all nodes reachable by $u$ using at most one route. If $u$ and $v$ is reachable within two routes, then the intersection of $S(v)$ and $S(u)$ is non-empty. We need to prove that the intersection of all $S(l_i)$ is non-empty. 570 571 If $l_i$, $l_j$, and $l_k$ are pairwise reachable within two paths, then the intersection of $S(l_i)$, $S(l_j)$, and $S(l_k)$ must be pairwise non-empty. Since the graph is a tree, it follows trivially that intersection of $S(l_i)$, $S(l_j)$, and $S(l_k)$ must be non-empty. We can generalize this to all leaves, thus proving the sufficiency part. 572 573 To check if an answer exists or not, we can use this [trick from ko_osaga](https://codeforces.com/blog/entry/51740?#comment-356857) to find how many $S(l_i)$ covers each node in $\mathcal O(n)$. The answer is YES when there is a node $c$ that is covered by all $S(l_i)$. 574 575 To find the two candidates when the answer is NO, notice that one of them is the first leaf $l_x$ such that there is no node $c$ that is covered by $S(l_1), \ldots, S(l_x)$. We can find $l_x$ with binary search. To find the other one, root the tree at $l_x$ and define $lift_u$ as the lowest node reachable by $u$ using at most one route. The other candidate is a node $l_y$ such that $lift_{l_y}$ is not in $S(l_x)$. 576 577 Time complexity: $\mathcal O(n \log n)$. 578 579 Tester's solution: Root the tree at some non-leaf vertex. Define $lift_u$ as the lowest node (minimum depth) reachable by $u$ using at most one route. Take the node $v$ with the deepest (maximum depth) $lift_v$. Then the answer for this problem is $\texttt{YES}$ iff for every leaf $l$, either $l$ lie in $lift_v$ 's subtree or $l$ has a path to $lift_v$. 580 581 **Implementation 1** 582 583 ``` 584 #include <bits/stdc++.h> 585 586 using namespace std; 587 588 const int N = 5e5 + 5; 589 const int LOG = 19; 590 591 /// lca stuff 592 int tin[N], timer = 0; 593 vector<int> path, rmq[LOG]; 594 595 /// some tree stuff 596 vector<int> adj[N], leaf, topo; 597 int n, m, par[N], val[N]; 598 599 /// trips 600 vector<int> trip[N]; 601 602 void dfs_pre(int u) { 603 topo.push_back(u); 604 tin[u] = timer++; 605 for (int v : adj[u]) 606 if (v != par[u]) { 607 path.push_back(u); 608 rmq[0].push_back(tin[u]); 609 par[v] = u; dfs_pre(v); 610 } 611 } 612 613 int get_min(int l, int r) { 614 int k = 31 - __builtin_clz(r - l); 615 return min(rmq[k][l], rmq[k][r - (1 << k)]); 616 } 617 618 int lca(int u, int v) { 619 if (u == v) return u; 620 tie(u, v) = minmax(tin[u], tin[v]); 621 return path[get_min(u, v)]; 622 } 623 624 int lca_reroot(int r, int u, int v) { 625 return lca(r, u) ^ lca(r, v) ^ lca(u, v); 626 } 627 628 void calc_val() { 629 for (int u : topo) 630 for (int v : adj[u]) 631 if (v != par[u]) val[u] += val[v]; 632 } 633 634 void add(int u) { 635 for (int v : trip[u]) 636 if (v < 0) val[-v]--; 637 else val[v]++; 638 } 639 640 bool check(int l) { 641 for (int u = 1; u <= n; u++) val[u] = 0; 642 for (int i = 0; i < l; i++) add(leaf[i]); 643 calc_val(); 644 for (int u = 1; u <= n; u++) 645 if (val[u] == l) return true; 646 return false; 647 } 648 649 void solve() { 650 cin >> n >> m; 651 652 /// reset 653 for (int i = 1; i <= n; i++) { 654 adj[i].clear(); trip[i].clear(); 655 } 656 timer = 0; leaf.clear(); topo.clear(); 657 path.clear(); rmq[0].clear(); 658 659 for (int i = 1; i < n; i++) { 660 int u, v; cin >> u >> v; 661 adj[u].push_back(v); 662 adj[v].push_back(u); 663 } 664 /// leaves only 665 for (int i = 1; i <= m; i++) { 666 int u, v; cin >> u >> v; 667 if (adj[u].size() == 1) 668 trip[u].push_back(v); 669 if (adj[v].size() == 1) 670 trip[v].push_back(u); 671 } 672 673 if (n == 1) { 674 cout << "YES\n"; return; 675 } 676 677 /// prepare 678 dfs_pre(1); 679 reverse(topo.begin(), topo.end()); 680 for (int k = 1; (1 << k) <= n; k++) { 681 rmq[k].resize(n - (1 << k) + 1); 682 for (int i = 0; i + (1 << k) <= n; i++) 683 rmq[k][i] = min(rmq[k - 1][i], 684 rmq[k - 1][i + (1 << (k - 1))]); 685 } 686 687 for (int u = 1; u <= n; u++) 688 if (adj[u].size() == 1) { 689 leaf.push_back(u); 690 trip[u].push_back(u); 691 sort(trip[u].begin(), trip[u].end(), 692 [&](int x, int y) { 693 return tin[x] < tin[y];}); 694 int l = trip[u].size(); 695 for (int i = 0; i + 1 < l; i++) 696 trip[u].push_back(-lca 697 (trip[u][i], trip[u][i + 1])); 698 trip[u].push_back(-par[lca 699 (trip[u][0], trip[u][l - 1])]); 700 } 701 702 /// find longest prefix of leaves 703 int l = 0; 704 for (int k = LOG - 1; k >= 0; k--) 705 if (l + (1 << k) <= leaf.size() 706 && check(l + (1 << k))) l += 1 << k; 707 708 if (l == leaf.size()) { 709 cout << "YES\n"; return; 710 } 711 712 cout << "NO\n"; 713 714 for (int u = 1; u <= n; u++) val[u] = 0; 715 add(leaf[l]); calc_val(); 716 717 for (int u : leaf) { 718 bool good = false; 719 for (int v : trip[u]) { 720 if (v <= 0) break; 721 if (val[lca_reroot(leaf[l], u, v)]) { 722 good = true; break; 723 } 724 } 725 if (!good) { 726 cout << leaf[l] << ' ' << u << '\n'; 727 return; 728 } 729 } 730 } 731 732 int main() { 733 cin.tie(0)->sync_with_stdio(0); 734 735 int t; cin >> t; 736 737 while (t--) solve(); 738 } 739 ``` 740 741 **Implementation 2** 742 743 ``` 744 #include<bits/stdc++.h> 745 746 using namespace std; 747 748 typedef long long ll; 749 const ll INF = 1e18; 750 const int maxn = 2e6 + 10; 751 const int mod = 1e9 + 7; 752 const int mo = 998244353; 753 using pi = pair < ll, ll > ; 754 using vi = vector < ll > ; 755 using pii = pair < pair < ll, ll > , ll > ; 756 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 757 vector < int > G[maxn]; 758 int n, m; 759 int h[maxn]; 760 int eu[maxn]; 761 pair < int, int > rmq[maxn][21]; 762 int l = 0; 763 int st[maxn]; 764 int out[maxn]; 765 int low[maxn]; 766 pair < int, int > ed[maxn]; 767 int par[maxn]; 768 int ok[maxn]; 769 int d[maxn]; 770 void dfs(int u, int pa) { 771 eu[++l] = u; 772 st[u] = l; 773 for (auto v: G[u]) { 774 if (v == pa) continue; 775 par[v] = u; 776 h[v] = h[u] + 1; 777 dfs(v, u); 778 eu[++l] = u; 779 } 780 out[u] = l; 781 } 782 void init() { 783 for (int j = 1; (1 << j) <= l; j++) { 784 for (int i = 1; i <= l; i++) { 785 rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]); 786 } 787 } 788 } 789 int LCA(int u, int v) { 790 if (st[u] > st[v]) { 791 swap(u, v); 792 } 793 int k = log2(st[v] - st[u] + 1); 794 return min(rmq[st[u]][k], rmq[st[v] - (1 << k) + 1][k]).second; 795 } 796 bool check(int u, int pa, int c) { 797 if (st[pa] <= st[c] && st[c] <= out[pa]) { 798 if (st[c] <= st[u] && st[u] <= out[c]) { 799 return true; 800 } 801 return false; 802 } 803 return false; 804 } 805 void solve() { 806 cin >> n >> m; 807 l = 0; 808 for (int i = 1; i <= n; i++) { 809 G[i].clear(); 810 } 811 for (int i = 1; i < n; i++) { 812 int x, y; 813 cin >> x >> y; 814 G[x].push_back(y); 815 G[y].push_back(x); 816 } 817 dfs(1, -1); 818 for (int i = 1; i <= l; i++) { 819 rmq[i][0] = {st[eu[i]], eu[i]}; 820 } 821 init(); 822 for (int i = 1; i <= n; i++) { 823 low[i] = i; 824 ok[i] = 0; 825 } 826 for (int i = 1; i <= m; i++) { 827 int x, y; 828 cin >> x >> y; 829 ed[i] = {x, y}; 830 int u = LCA(x, y); 831 if (h[low[x]] > h[u]) { 832 low[x] = u; 833 } 834 if (h[low[y]] > h[u]) { 835 low[y] = u; 836 } 837 } 838 int need = 0; 839 for (int i = 2; i <= n; i++) { 840 if (low[i] != 1 && G[i].size() == 1) { 841 if (need == 0 || h[low[need]] < h[low[i]]) { 842 need = i; 843 } 844 } 845 } 846 if (need == 0) { 847 cout << "YES\n"; 848 return; 849 } 850 for (int i = 1; i <= m; i++) { 851 int u = LCA(ed[i].first, ed[i].second); 852 if (G[ed[i].first].size() == 1 && check(ed[i].second, u, low[need])) { 853 ok[ed[i].first] = 1; 854 } 855 if (G[ed[i].second].size() == 1 && check(ed[i].first, u, low[need])) { 856 ok[ed[i].second] = 1; 857 } 858 } 859 for (int i = 1; i <= n; i++) { 860 if (G[i].size() == 1) { 861 if (st[low[need]] <= st[i] && st[i] <= out[low[need]]) { 862 continue; 863 } 864 if (ok[i] == 0) { 865 cout << "NO\n"; 866 cout << need << " " << i << "\n"; 867 return; 868 } 869 } 870 } 871 cout << "YES\n"; 872 return; 873 } 874 signed main() { 875 cin.tie(0), cout.tie(0) -> sync_with_stdio(0); 876 int t; 877 cin >> t; 878 while (t--) solve(); 879 return 0; 880 } 881 ``` 882 883 **sorry gamegame** 884 885  886 887 ## [1827F - Copium Permutation](/contest/1827/problem/F "Codeforces Round 873 (Div. 1)") 888 889 Idea: [lanhf](/profile/lanhf "Master lanhf") 890 Preparation: [lanhf](/profile/lanhf "Master lanhf") 891 892 **Solution** 893 894 ### Solve the problem for fixed $k$ 895 896 Call the last $n-k$ elements as special numbers. 897 898 **Observation**: In optimal rearrangement, every maximal segment of special numbers will be placed on consecutive positions in either ascending order or descending order. For simplicity, from now on we will call maximal segment of special number as maximal segment. 899 900 For example, take a permutation $p=[7, 5, 8, 1, 4, 2, 6, 3]$ and $k=2$, the maximal segments are $[1, 4]$, $[6, 6]$ and $[8, 8]$. 901 902 We divide the set of copium subarrays into three parts, one for those lie entirely on prefix $p[1..k]$, one for those lie entirely on suffix $p[k+1..n]$, and one for the rest. The number of subarrays in the first part can be calculated with the algorithm used in [526F - Pudding Monsters](/contest/526/problem/F "ZeptoLab Code Rush 2015"). The number of subarrays in the second part can be easily deduced from above observation. 903 904 Define an array $good=[good_1,good_2,\ldots,good_m]$ such that for each $i$: $good_i \lt good_{i+1}$ and subarray $p[good_i..k]$ contains consecutive nonspecial numbers. 905 906 For example, take a permutation $p=[1, 5, 4,3,7,8,9,2,10,6]$ and $k=5$, then $good=[1, 4, 5]$. 907 908 We will process $good$ array from right to left while adding special numbers from left to right. Let us consider $good_i$, first add all special numbers which are missing from subarray $[good_i, k]$ at the end of current permutation. If $[good_i, k]$ is not already copium, we increase our answer by one. Denote $mn_i$ and $mx_i$ as the minimum and maximum number in subarray $[good_i, k]$. Loot at two maximal segments, one contains $mn_i-1$ and one contains $mx_i+1$. We can place them here to increase the answer. 909 910 For example, let $n=10$, $k=5$, $good_i=3$ and the current permutation $p=[1, 10, 4, 5, 7, 6]$. The two maximal segments are $[2, 3]$ and $[8, 9]$. We can place them like $[1, 10, 4, 5, 7, 6, 8, 9, 3, 2]$ to increase the answer by 4. Furthermore, we can see that three good positions $3$, $4$ and $5$ benefit from maximal segment $[8, 9]$. In general, consider consecutive good positions $good_i, good_{i+1},\ldots, good_j$ satisfying $mx_i=mx_{i+1}=\ldots=mx_j$, all of them can benefit from the same maximal segment if for all $i\le x \lt j$, subarray $[good_x..good_{x+1}-1]$ is copium $(*)$. 911 912 There is a similar condition when we consider consecutive good positions having the same $mn$. So the algorithm goes like this: For each value of $mn$ and $mx$, find the longest segment of good positions satisfying condition $(*)$, then multiply with the length of corresponding maximal segment and add to the answer. 913 914 ### Solve for each $k$ 915 916 We will calculate the answer for each $k$ from $0$ to $n$ in this order. We will store the longest segment for each prefix of $mn$-equivalent and $mx$-equivalent positions. Note that when going from $k-1$ to $k$, only a suffix of $good$ will no longer be good, so we can manually delete them one by one from right to left, then add $k$. There will be at most $2$ good positions we need to consider. The first one, of course, is $k$. If $p_{k-1} \lt p_k$ or $p_{k-1} \gt p_k$, let $j$ be the last position satisfying $p_j \gt p_k$ or $p_j \lt p_k$, the second one is the first good position after $j$ and it satisfies a property: It must be the last position in the $mn$-equivalent or $mx$-equivalent positions. The proof is left as an exercise. Therefore, updating this position will not affect the positions behind it. The overall complexity is $\mathcal{O}(n\log n)$. 917 918 **Implementation** 919 920 ``` 921 #include <bits/stdc++.h> 922 923 using namespace std; 924 925 using ll = long long; 926 927 const int N = 200005; 928 const int LOG = 18; 929 930 int n, a[N], pos[N]; 931 int lef[N], rig[N]; 932 933 vector<int> st_max, st_min; 934 935 void connect(int x, int y) { 936 rig[x] = y; lef[y] = x; 937 } 938 939 struct range_min { 940 vector<int> spt[LOG]; 941 942 void build() { 943 for (int k = 0; k < LOG; k++) 944 spt[k].resize(n + 1); 945 for (int i = 1; i <= n; i++) 946 spt[0][i] = pos[i]; 947 for (int k = 1; k < LOG; k++) 948 for (int i = 1; i + (1 << k) <= n + 1; i++) { 949 spt[k][i] = min(spt[k - 1][i], 950 spt[k - 1][i + (1 << (k - 1))]); 951 } 952 } 953 954 int get_min_pos(int l, int r) { 955 int k = __lg(r - l + 1); 956 return min(spt[k][l], spt[k][r - (1 << k) + 1]); 957 } 958 } rmq; 959 960 int get_min(int i) { 961 return a[*lower_bound(st_min.begin(), st_min.end(), i)]; 962 } 963 964 int get_max(int i) { 965 return a[*lower_bound(st_max.begin(), st_max.end(), i)]; 966 } 967 968 struct segtree1 { 969 #define il i * 2 970 #define ir i * 2 + 1 971 struct node { 972 int val, cnt, tag; 973 }; 974 975 node tree[N * 4]; 976 977 void build(int i, int l, int r) { 978 tree[i] = {l, 1, 0}; 979 if (l < r) { 980 int m = (l + r) / 2; 981 build(il, l, m); 982 build(ir, m + 1, r); 983 } 984 } 985 986 void add(int i, int l, int r, int x, int y, int v) { 987 if (l >= x && r <= y) { 988 tree[i].val += v; tree[i].tag += v; return; 989 } 990 991 int m = (l + r) / 2; 992 if (m >= x) add(il, l, m, x, y, v); 993 if (m < y) add(ir, m + 1, r, x, y, v); 994 995 tree[i].val = tree[il].val; 996 tree[i].cnt = tree[il].cnt; 997 998 if (tree[i].val > tree[ir].val) { 999 tree[i].val = tree[ir].val; 1000 tree[i].cnt = tree[ir].cnt; 1001 } else if (tree[i].val == tree[ir].val) 1002 tree[i].cnt += tree[ir].cnt; 1003 1004 tree[i].val += tree[i].tag; 1005 } 1006 #undef il 1007 #undef ir 1008 } seg1; 1009 1010 struct copium { 1011 int curr, maxx, type; 1012 1013 copium() {} 1014 1015 copium(int curr, int maxx, int type): 1016 curr(curr), maxx(max(maxx, curr)), type(type) {} 1017 }; 1018 1019 copium lmin[N], lmax[N]; 1020 ll prefix, middle, suffix; 1021 1022 /// cancer 1023 void calc(int i, int j, bool recalc) { 1024 int imin = get_min(i), imax = get_max(i); 1025 int jmin = get_min(j), jmax = get_max(j); 1026 int type; 1027 if (recalc) { 1028 middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1); 1029 middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 1030 } 1031 1032 if (imax == jmax) { 1033 if (!recalc) 1034 middle -= 1ll * lmax[i].maxx * (rig[imax] - imax - 1); 1035 1036 if (jmin - imin == j - i) type = 0; 1037 else if (imin + j - i == lef[jmin] + 1) type = 1; 1038 else type = 2; 1039 1040 if (type == 2) lmax[j] = copium(1, lmax[i].maxx, type); 1041 else if (lmax[i].type == 0) 1042 lmax[j] = copium(lmax[i].curr + 1, lmax[i].maxx, type); 1043 else lmax[j] = copium(2, lmax[i].maxx, type); 1044 1045 } else lmax[j] = {1, 1, 3}; 1046 if (imin == jmin) { 1047 if (!recalc) 1048 middle -= 1ll * lmin[i].maxx * (imin - lef[imin] - 1); 1049 1050 if (imax - jmax == j - i) type = 0; 1051 else if (imax + i - j == rig[jmax] - 1) type = 1; 1052 else type = 2; 1053 1054 if (type == 2) lmin[j] = copium(1, lmin[i].maxx, type); 1055 else if (lmin[i].type == 0) 1056 lmin[j] = copium(lmin[i].curr + 1, lmin[i].maxx, type); 1057 else lmin[j] = copium(2, lmin[i].maxx, type); 1058 1059 } else lmin[j] = {1, 1, 3}; 1060 1061 middle += 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1); 1062 middle += 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 1063 } 1064 1065 int main() { 1066 cin.tie(0)->sync_with_stdio(0); 1067 int t; cin >> t; 1068 while (t--) { 1069 cin >> n; 1070 for (int i = 1; i <= n; i++) { 1071 cin >> a[i]; pos[a[i]] = i; 1072 lef[i] = rig[i] = 0; 1073 } 1074 1075 st_min.assign(1, 0); 1076 st_max.assign(1, 0); 1077 1078 set<int> sorted; 1079 sorted.insert(0); 1080 sorted.insert(n + 1); 1081 1082 prefix = 0; 1083 suffix = 1ll * n * (n + 1) / 2; 1084 middle = 0; 1085 1086 // k = 0 1087 cout << suffix << ' '; 1088 1089 lef[n] = 0; rig[0] = n; 1090 1091 seg1.build(1, 1, n); rmq.build(); 1092 1093 vector<int> good; 1094 1095 for (int i = 1; i <= n; i++) { 1096 1097 while (good.size()) { 1098 int j = good.back(); 1099 int jmin = get_min(j), jmax = get_max(j); 1100 1101 if (rmq.get_min_pos(min(jmin, a[i]), max(jmax, a[i])) < j) { 1102 middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1); 1103 middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 1104 good.pop_back(); 1105 if (good.size()) { 1106 if (lmax[j].type < 3) 1107 middle += 1ll * lmax[good.back()].maxx * (rig[jmax] - jmax - 1); 1108 if (lmin[j].type < 3) 1109 middle += 1ll * lmin[good.back()].maxx * (jmin - lef[jmin] - 1); 1110 } 1111 } else break; 1112 } 1113 1114 if (good.size()) { 1115 int j = good.back(); 1116 int jmin = get_min(j), jmax = get_max(j); 1117 middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1); 1118 middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 1119 } 1120 1121 auto it = sorted.upper_bound(a[i]); 1122 suffix -= 1ll * (*it - a[i]) * (a[i] - *prev(it)); 1123 connect(*prev(it), a[i]); connect(a[i], *it); 1124 sorted.insert(a[i]); 1125 1126 while (st_max.size() > 1 && a[st_max.back()] < a[i]) { 1127 seg1.add(1, 1, n, st_max[st_max.size() - 2] + 1, 1128 st_max.back(), a[i] - a[st_max.back()]); 1129 st_max.pop_back(); 1130 } 1131 1132 while (st_min.size() > 1 && a[st_min.back()] > a[i]) { 1133 seg1.add(1, 1, n, st_min[st_min.size() - 2] + 1, 1134 st_min.back(), a[st_min.back()] - a[i]); 1135 st_min.pop_back(); 1136 } 1137 1138 st_max.push_back(i); st_min.push_back(i); 1139 1140 if (good.size()) { 1141 int j = good.back(); 1142 int jmin = get_min(j), jmax = get_max(j); 1143 middle += 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1); 1144 middle += 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 1145 calc(j, i, 0); 1146 } else { 1147 lmax[i] = lmin[i] = {1, 1, 3}; 1148 middle += rig[a[i]] - lef[a[i]] - 2; 1149 } 1150 1151 good.push_back(i); 1152 if (st_min.size() >= 2) { 1153 int k = upper_bound(good.begin(), good.end(), 1154 st_min[st_min.size() - 2]) - good.begin(); 1155 if (k > 0 && k < good.size()) 1156 calc(good[k - 1], good[k], 1); 1157 } 1158 if (st_max.size() >= 2) { 1159 int k = upper_bound(good.begin(), good.end(), 1160 st_max[st_max.size() - 2]) - good.begin(); 1161 if (k > 0 && k < good.size()) 1162 calc(good[k - 1], good[k], 1); 1163 } 1164 1165 cout << prefix + good.size() + middle + suffix << ' '; 1166 1167 prefix += seg1.tree[1].cnt; 1168 } 1169 cout << '\n'; 1170 } 1171 } 1172 ```