1830.md (43272B)
1 Source: https://codeforces.com/blog/entry/116527 2 3 ## [1831A — Twin Permutations](https://codeforces.com/contest/1831/problem/A) 4 5 Author: [Gheal](/profile/Gheal "Candidate Master Gheal") 6 7 **Hints** 8 9 **Hint 1** 10 11 If $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$. 12 13 **Hint 2** 14 15 Building on the idea from the first hint, can we build a permutation $b$ such that $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$? 16 17 **Solution** 18 19 Since $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$. 20 21 Therefore, any permutation $b$ which satisfies $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$ is a valid answer. 22 23 If $b_i=n+1-a_i$, then: 24 25 1. $b$ is a permutation; 26 2. $a_1+b_1=a_2+b_2=\ldots=a_n+b_n=n+1$ 27 28 Consequently, $b=[n+1-a_1,n+1-a_2,\ldots,n+1-a_i,\ldots,n+1-a_n]$ is a valid answer. 29 30 Time complexity per test case : $O(N)$ 31 32 **Code (Gheal, C++)** 33 34 ``` 35 #include<bits/stdc++.h> 36 37 using namespace std; 38 typedef long long ll; 39 void tc(){ 40 ll n; 41 cin>>n; 42 for(ll i=0;i<n;i++){ 43 ll x; 44 cin>>x; 45 cout<<n+1-x<<' '; 46 } 47 cout<<'\n'; 48 } 49 int main() 50 { 51 ios_base::sync_with_stdio(false); cin.tie(0); 52 ll t; cin>>t; while(t--) 53 tc(); 54 return 0; 55 } 56 ``` 57 58 **Rate Problem** 59 60 Good problem 61 62 Ok problem 63 64 Bad problem 65 66 Didn't solve it, idk 67 68 ## [1831B — Array Merging](https://codeforces.com/contest/1831/problem/B) 69 70 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 71 72 **Hints** 73 74 **Hint 1** 75 76 When we merge two arrays $a$ and $b$, we can force the resulting array to have $[a_{l_1},a_{l_1+1},\ldots,a_{r_1},b_{l_2},b_{l_2+1},\ldots,b_{r_1}]$ as a subarray, for some $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le n$. 77 78 **Hint 2** 79 80 If $a_{l_1}=b_{l_1}$, then we can achieve a contiguous sequence of $(r_1-l_1+1)+(r_2-l_2+1)$ equal elements in the resulting array. 81 82 **Solution** 83 84 Let $max_a(x)$ be the length of the longest subarray from $a$ containing only elements equal to $x$. If $x$ doesn't appear in $a$, then $max_a(x)=0$. 85 86 Similarly, let $max_b(x)$ be the length of the longest subarray from $b$ containing only elements equal to $x$. If $x$ doesn't appear in $b$, then $max_b(x)=0$. 87 88 $max_a$ and $max_b$ can be computed in $O(N)$ by scanning the array while updating current maximal subarray. 89 90 When merging two arrays, it is possible to force a particular subarray $[a_{l_1},a_{l_1+1},\ldots,a_{r_1}]$ to be adjacent to another particular subarray $[b_{l_2},b_{l_2+1},\ldots,b_{r_2}]$ in the merged array. 91 92 **Proof** 93 94 We can construct the merged array as follows: 95 96 $[a_1,a_2,\ldots,a_{l_1-1}]+[b_1,b_2,\ldots,b_{l_2-1}]+[a_{l_1},a_{l_1+1},\ldots,a_{r_1},b_{l_2},b_{l_2+1},\ldots,b_{r_2}]+[\ldots]$ 97 98 If $a_{l_1}=b_{l_2}$, then the merged array will have a subarray consisting of $(r_1-l_1+1)+(r_2-l_2+1)$ equal elements. 99 100 Therefore, the answer is equal to: 101 102 $max_{i=1}^{2 \cdot n}(max_a(i)+max_b(i))$ 103 104 Time complexity per testcase: $O(N)$. 105 106 **Code (tibinyte, C++)** 107 108 ``` 109 #include <bits/stdc++.h> 110 111 using namespace std; 112 113 int32_t main() 114 { 115 cin.tie(nullptr)->sync_with_stdio(false); 116 int q; 117 cin >> q; 118 while (q--) 119 { 120 int n; 121 cin >> n; 122 vector<int> a(n + 1); 123 vector<int> b(n + 1); 124 for (int i = 1; i <= n; ++i) 125 { 126 cin >> a[i]; 127 } 128 for (int i = 1; i <= n; ++i) 129 { 130 cin >> b[i]; 131 } 132 vector<int> fa(n + n + 1); 133 vector<int> fb(n + n + 1); 134 int p = 1; 135 for (int i = 2; i <= n; ++i) 136 { 137 if (a[i] != a[i - 1]) 138 { 139 fa[a[i - 1]] = max(fa[a[i - 1]], i - p); 140 p = i; 141 } 142 } 143 fa[a[n]] = max(fa[a[n]], n - p + 1); 144 145 p = 1; 146 for (int i = 2; i <= n; ++i) 147 { 148 if (b[i] != b[i - 1]) 149 { 150 fb[b[i - 1]] = max(fb[b[i - 1]], i - p); 151 p = i; 152 } 153 } 154 fb[b[n]] = max(fb[b[n]], n - p + 1); 155 156 int ans = 0; 157 for (int i = 1; i <= n + n; ++i) 158 { 159 ans = max(ans, fa[i] + fb[i]); 160 } 161 162 cout << ans << '\n'; 163 } 164 } 165 ``` 166 167 **Rate problem** 168 169 Good problem 170 171 Ok problem 172 173 Bad problem 174 175 Didn't solve it, idk 176 177 ## [1830A — Copil Copac Draws Trees](https://codeforces.com/contest/1830/problem/A) 178 179 Author: [alecs](/profile/alecs "Candidate Master alecs") 180 181 **Hints** 182 183 **Hint 1** 184 185 What is the answer if $n=3$? 186 187 **Hint 2** 188 189 The previous case can be generalised to find the answer for any tree. 190 191 **Solution** 192 193 This problem can be solved via dynamic programming. From here on out, step $1$ from the statement will be called a "scan". 194 195 Let $dp[i]$ be the number of scans needed to activate node $i$, and $id[i]$ be the index (in the order from the input) of the edge which activated node $i$. 196 197 Intially, since only $1$ is active, $dp[1]=1$ and $id[1]=0$. 198 199 We will perform a dfs traversal starting from node $1$. When we process an edge $(u,v)$, one of the following two cases can happen: 200 201 1. If $index((u,v)) \ge id[u]$, we can visit $v$ in the same scan as $u$: 202 203 $dp[v]=dp[u]$, $id[v]=index((u,v))$ 204 205 1. If $index((u,v)) \lt id[u]$, $v$ will be visited in the next scan after $dp[u]$: 206 207 $dp[v]=dp[u]+1$, $id[v]=index((u,v))$ 208 209 The answer is $max_{i=1}^n(dp[i])$. 210 211 Time complexity per test case: $O(n)$ 212 213 **Code (Gheal, C++)** 214 215 ``` 216 #include<bits/stdc++.h> 217 218 using namespace std; 219 const int NMAX = 2e5+5; 220 int dp[NMAX], id[NMAX]; 221 vector<pair<int,int>> edg[NMAX]; 222 void dfs(int u){ 223 for(auto it : edg[u]){ 224 if(dp[it.first] == 0){ 225 dp[it.first] = dp[u] + (it.second <= id[u]); 226 id[it.first] = it.second; 227 dfs(it.first); 228 } 229 } 230 } 231 void tc(){ 232 int n; 233 cin>>n; 234 for(int i=1; i<=n; i++) dp[i] = id[i] = 0, edg[i].clear(); 235 for(int i=1; i<n; i++){ 236 int u,v; 237 cin>>u>>v; 238 edg[u].push_back({v,i}); 239 edg[v].push_back({u,i}); 240 } 241 dp[1] = 1; 242 dfs(1); 243 int ans = 0; 244 for(int i=1; i<=n; i++) ans=max(ans,dp[i]); 245 cout<<ans<<'\n'; 246 } 247 int main() 248 { 249 ios_base::sync_with_stdio(false); 250 int t; 251 cin>>t; 252 while(t--) 253 tc(); 254 return 0; 255 } 256 ``` 257 258 **Code (alecs, C++)** 259 260 ``` 261 #include <bits/stdc++.h> 262 263 const int NMAX = 3e5 + 5, INF = 1e9; 264 265 int n, f[NMAX], d[NMAX]; 266 std :: vector < std :: pair < int, int > > G[NMAX]; 267 268 void DFS(int node, int t) { 269 f[node] = true; 270 271 for (int i = 0; i < G[node].size(); ++ i) { 272 int u = G[node][i].first, c = G[node][i].second; 273 274 if (f[u] == false) { 275 d[u] = (c < t) + d[node]; 276 DFS(u, c); 277 } 278 } 279 280 return; 281 } 282 283 int main() { 284 std :: ios_base :: sync_with_stdio(false); 285 std :: cin.tie(nullptr); 286 287 int tc; 288 289 std :: cin >> tc; 290 291 while (tc --) { 292 std :: cin >> n; 293 294 for (int i = 1, u, v; i < n; ++ i) { 295 std :: cin >> u >> v; 296 297 G[u].push_back({v, i}); 298 G[v].push_back({u, i}); 299 } 300 301 for (int i = 1; i <= n; ++ i) 302 f[i] = false; 303 304 d[1] = 0; 305 DFS(1, n); 306 307 int Max = 0; 308 309 for (int i = 1; i <= n; ++ i) 310 Max = std :: max(Max, d[i]); 311 312 std :: cout << Max << "\n"; 313 314 for (int i = 1; i <= n; ++ i) 315 G[i].clear(); 316 } 317 318 return 0; 319 } 320 ``` 321 322 **Rate problem** 323 324 Good problem 325 326 Ok problem 327 328 Bad problem 329 330 Didn't solve it, idk 331 332 ## [1830B — The BOSS Can Count Pairs](https://codeforces.com/contest/1830/problem/B) 333 334 Author: [Gheal](/profile/Gheal "Candidate Master Gheal") 335 336 **Hints** 337 338 **Hint 1** 339 340 Since $b_i \le n$ and $b_j \le n$, $b_i+b_j = a_i \cdot a_j \le 2 \cdot n$. 341 342 **Hint 2** 343 344 Since $a_i \cdot a_j \le 2 \cdot n$, then $\min(a_i,a_j) \le \sqrt{2 \cdot n}$. 345 346 **Solution** 347 348 Since $b_i \le n$ and $b_j \le n$, $b_i+b_j = a_i \cdot a_j \le 2 \cdot n$. Therefore, $\min(a_i,a_j) \le \sqrt{2 \cdot n}$. 349 350 Let $lim=\sqrt{2 \cdot n}$ and $fr[a_i][b_i]$ be the number of pairs $(a_i,b_i)$ from the input such that $a_i \le lim$. 351 352 A pair $(i,j)$ is *good* if it satisfies $a_i \cdot a_j=b_i+b_j$. 353 354 Firstly, we'll count the number of good pairs $(i,j)$ such that $a_i=a_j$. Since $min(a_i,a_j) \le lim$, we can see that $a_i=a_j \le lim$. 355 356 This sum can be written as: 357 358 $\frac{\sum_{i=1}^{n}fr[a_i][a_i \cdot a_i - b_i]-\sum_{i=1}^{lim}fr[i][\frac{i \cdot i}{2}]}{2}$ 359 360 The remaining good pairs will have $a_i \neq a_j$, and instead of counting the pairs which have $i \lt j$, we can count the pairs which have $a_i \gt a_j$. 361 362 Since $a_j=min(a_i,a_j)$, we can say that $a_j \le lim$. 363 364 Substituting $a_j$ for $j$, this second sum can be written as: 365 366 $\sum_{i=1}^n \sum_{j=1}^{min(a_i-1,\frac{2\cdot n}{a_i})}fr[j][a_i \cdot j-b_i]$ 367 368 Since we've already established that $j \le lim = \sqrt{2 \cdot n}$, calculating this sum takes $O(n\sqrt{n})$ time. 369 370 **Be especially careful when calculating these sums, as $a_i \cdot a_i - b_i$ and $a_i \cdot j-b_i$ can end up being either negative or greater than $n$.** 371 372 Time complexity per testcase: $O(n \sqrt n)$ 373 374 **Code (Gheal, C++)** 375 376 ``` 377 #include<bits/stdc++.h> 378 379 using namespace std; 380 typedef long long ll; 381 const ll NMAX=2e5+5,SQRMAX=635,MOD=1e9+7; 382 383 int fr[SQRMAX][NMAX]; 384 ll a[NMAX],b[NMAX]; 385 void tc(){ 386 ll n,ans=0; 387 cin>>n; 388 ll lim=sqrt(n*2); 389 for(ll i=0;i<n;i++){ 390 cin>>a[i]; 391 } 392 for(ll i=0;i<n;i++){ 393 cin>>b[i]; 394 if(a[i]<=lim) 395 fr[a[i]][b[i]]++; 396 } 397 for(ll i=0;i<n;i++){ 398 if(a[i]<=lim){ 399 if(a[i]*a[i]-b[i]>=1 && a[i]*a[i]-b[i]<=n) 400 ans+=fr[a[i]][a[i]*a[i]-b[i]]; 401 } 402 } 403 for(ll i=2;i<=lim;i+=2) 404 ans-=fr[i][i*i/2]; 405 ans/=2; 406 407 for(ll i=0;i<n;i++){ 408 for(ll j=1;j<=lim && j<a[i] && j*a[i]<=2*n;j++){ 409 if(j*a[i]-b[i]>=1 && j*a[i]-b[i]<=n) 410 ans+=fr[j][j*a[i]-b[i]]; 411 } 412 } 413 for(ll i=0;i<n;i++){ 414 if(a[i]<=lim) 415 fr[a[i]][b[i]]=0; 416 } 417 cout<<ans<<'\n'; 418 } 419 int main() 420 { 421 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 422 ll t; 423 cin>>t; 424 while(t--) 425 tc(); 426 return 0; 427 } 428 ``` 429 430 **Code (Vladithur, Python)** 431 432 ``` 433 for _ in range(int(input())): 434 n = int(input()) 435 436 ta = list(map(int, input().split())) 437 tb = list(map(int, input().split())) 438 439 a = [(x, y) for x, y in zip(ta, tb)] 440 a.sort() 441 442 cnt = [0] * (2 * n + 1) 443 pr = 0 444 ans = 0 445 446 for i in range(n): 447 if pr != a[i][0]: 448 pr = a[i][0] 449 450 if pr * pr > 2 * n: 451 break 452 453 cnt = [0] * (2 * n + 1) 454 for j in range(i + 1, n): 455 t = a[i][0] * a[j][0] - a[j][1] 456 if t >= 0 and t <= 2 * n: 457 cnt[t] += 1 458 459 ans += cnt[a[i][1]] 460 461 if i + 1 < n: 462 t = a[i][0] * a[i + 1][0] - a[i + 1][1] 463 if t >= 0 and t <= 2 * n: 464 cnt[t] -= 1 465 466 print(ans) 467 ``` 468 469 **Rate problem** 470 471 Good problem 472 473 Ok problem 474 475 Bad problem 476 477 Didn't solve it, idk 478 479 ## [1830C — Hyperregular Bracket Strings](https://codeforces.com/contest/1830/problem/C) 480 481 Author: [Gheal](/profile/Gheal "Candidate Master Gheal") 482 483 **Hints** 484 485 **Hint 1** 486 487 While not necessarily a hint, this problem cannot be solved without knowing that there are $C_n=\frac{1}{n+1}\binom{2n}{n}$ Regular Bracket Strings of length $2 \cdot n$. 488 489 **Hint 2** 490 491 What's the answer if $q=1$? 492 493 **Hint 3** 494 495 What's the answer if $q=2$ and the two intervals partially overlap? 496 497 **Hint 4** 498 499 Based on the previous hint, we can get rid of all partially overlapping intervals. The remaining intervals will have a tree-like structure. 500 501 **Hint 5** 502 503 Finding the tree is actually unnecessary and also very difficult. 504 505 **Hint 6** 506 507 The brackets on the positions covered by the same **subset** of intervals must form an RBS. 508 509 **Hint 7** 510 511 Hashing. Xor hashing specifically. 512 513 **Solution** 514 515 First and foremost, the number of regular bracket strings of length $2 \cdot n$ is equal to $C_n=\frac{1}{n+1}\binom{2n}{n}$. 516 517 Secondly, for a bracket string $\overline{s_1s_2 \ldots s_k}$, let: 518 519 $f(s_i) = \begin{cases} 1, & \text{if }s_i=\text{'('} \\ -1, & \text{if }s_i=\text{')'} \end{cases}$$\Delta_i=\sum_{j=1}^i f(s_j)$ 520 521 A bracket string $\overline{s_1s_2 \ldots s_k}$ is a regular bracket string if both of the following statements are true: 522 523 1. $\Delta_k=0$ 524 2. $\Delta_i \ge 0, i=\overline{1,k}$ 525 526 From now on we'll call a set of indices $i_1 \lt i_2 \lt \ldots \lt i_k$ a *group* if $\overline{s_{i_1}s_{i_2}\ldots s_{i_k}}$ must be an RBS. 527 528 There are two main cases to consider, both of which can be proven with the aforementioned conditions for a string to be an RBS: 529 530 **Case 1: Included intervals** 531 532 Let's consider two intervals $[l_1,r_1]$ and $[l_2,r_2]$ such that $l_1 \le l_2 \le r_2 \le r_1$. 533 534 The two groups formed by these intervals are: 535 536 * $[l_2,r_2]$ 537 * $[l_1,l_2-1] \cup [r_2+1,r_1]$ 538 539 **Case 2: Partially overlapping intervals** 540 541 Let's consider two intervals $[l_1,r_1]$ and $[l_2,r_2]$ such that $l_1 \lt l_2 \le r_1 \lt r_2$. 542 543 The three groups formed by these two intervals are: 544 545 * $[l_1,l_2-1]$ 546 * $[l_2,r_1]$ 547 * $[r_1+1,r_2]$ 548 549 By taking both of these cases into account, we can conclude that all indices $i_k$ covered by the same **subset** of intervals are part of the same group. 550 551 Finding the subset of intervals which cover a certain index $i$ can be implemented using difference arrays and xor hashing. 552 553 **How does xor hashing on difference arrays work?** 554 555 Each interval $[l_i,r_i]$ will be assigned a random 64-bit value $v_i$. 556 557 The value of a subset of intervals $i_1,i_2,\ldots,i_k$ is equal to $v_{i_1} \wedge v_{i_2} \wedge \ldots \wedge v_{i_k}$. 558 559 For each interval $[l_i,r_i]$, $\text{diff}[l_i] \wedge = v_i$, $\text{diff}[r_i+1] \wedge = v_i$. 560 561 The value of the subset of intervals which cover position $i$ is equal to $\text{diff}[1] \wedge \text{diff}[2] \wedge \ldots \wedge \text{diff}[i]$. 562 563 Time complexity: $O(maxn \cdot log(mod))$ for precomputing every $C_n$, and $O(k\cdot log(k))$ per test case. 564 565 **Code (Gheal, C++)** 566 567 ``` 568 #include<bits/stdc++.h> 569 570 using namespace std; 571 typedef long long ll; 572 const int NMAX=3e5+5, MOD=998244353; 573 574 mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); 575 uniform_int_distribution<ll> rnd(0,LLONG_MAX); 576 577 ll fact[NMAX], invfact[NMAX], C[NMAX]; 578 579 ll binPow(ll x, ll y){ 580 ll ans=1; 581 for(;y ;y>>=1, x = x*x%MOD) 582 if(y&1) 583 ans = ans*x%MOD; 584 return ans; 585 } 586 map<ll,ll> diff,freq; 587 void add_interval(ll l, ll r){ 588 ll Hash = rnd(gen); 589 diff[l] ^= Hash, diff[r+1] ^= Hash; 590 } 591 void tc(){ 592 ll n,k; 593 cin>>n>>k; 594 diff.clear(), freq.clear(); 595 add_interval(1,n); /// the initial string must be an RBS 596 597 for(ll i=0;i<k;i++){ 598 ll l,r; 599 cin>>l>>r; 600 add_interval(l,r); 601 } 602 ll Hash = diff[1]; 603 604 for(map<ll,ll> :: iterator it=next(diff.begin()); it!=diff.end(); it++){ 605 freq[Hash] += it->first - prev(it)->first; 606 Hash ^= it->second; 607 } 608 609 ll ans=1; 610 611 for(const auto& it : freq) 612 ans=ans*C[it.second]%MOD; 613 614 cout<<ans<<'\n'; 615 } 616 617 int main() 618 { 619 fact[0] = invfact[0] = 1; 620 for(ll i=1; i<NMAX; i++){ 621 fact[i] = fact[i-1] * i % MOD; 622 invfact[i] = binPow(fact[i], MOD - 2); 623 } 624 625 for(ll i=0; i*2<NMAX; i++) C[i*2] = fact[i*2] * invfact[i] % MOD * invfact[i+1] % MOD; 626 627 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 628 ll t; 629 cin>>t; 630 while(t--) 631 tc(); 632 return 0; 633 } 634 ``` 635 636 **Rate problem** 637 638 Good problem 639 640 Ok problem 641 642 Bad problem 643 644 Didn't solve it, idk 645 646 ## [1830D — Mex Tree](https://codeforces.com/contest/1830/problem/D) 647 648 Author: [Gheal](/profile/Gheal "Candidate Master Gheal") 649 650 **Hints** 651 652 **Hint 1** 653 654 Why is bipartite coloring not always optimal? 655 656 **Hint 2** 657 658 How good is a bipartite coloring actually? 659 660 **Solution** 661 662 Disclaimer: I ( [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") ) wanted to cut $O(n \sqrt{n})$ memory because I thought that setting 1024 MB memory limit would spoil the solution. So only blame me for this. 663 664 We will do a complementary problem which is finding the minimum loss of a coloring. The initial cost is the maximum possible cost, $n \cdot (n+1)$. 665 666 If we analyze how good a bipartite coloring of the given tree is we can note that $loss \le 2 \cdot n$ 667 668 Now suppose the tree has a connected component of size $k$. We can note that in such a coloring $loss \ge \frac{k \cdot (k+1)}{2}$ 669 670 By the $2$ claims above, we can note that in an optimal coloring, the maximum size $k$ of a connected component respects $\frac{k \cdot (k+1)}{2} \le 2 \cdot n$. Thus we can safely say $k \le \sqrt{4 \cdot n}$. 671 672 Now let $dp_{i,j,color}$ be the minimum loss if we color the subtree of $i$ and the connected component of vertex $i$ has size $j$. We can calculate this in a knapsack style by adding subtrees successively. The computation takes $O(n \cdot \sqrt{n})$ if we use the $7$-th trick from [this](https://codeforces.com/blog/entry/100910) blog. 673 674 Now we are only left to optimize memory, since now it's $O(n \cdot \sqrt{n})$. We can directly apply [this](https://codeforces.com/blog/entry/113453) to get linear memory. 675 676 However, the bound of $k \le \sqrt{4 \cdot n}$ is overestimated, for $n=200000$ it can be proven that the worst case for $k$ is $258$. 677 678 **Proof Sketch** 679 680 Assume have a connected component of size $k$ we want it to be colored $0$ across all optimal colorings. Then we can attach to each node some subtrees such that after flipping its whole subtree the total cost doesn't increase. We will assume all subtrees are leaves for simplicity. Doing such, we can get some inequalities about the number of leaves we need to attatch to each node. 681 682 In a star tree, the number of leaves we should attatch to nodes has the smallest sum. 683 684 **Code (tibinyte, C++)** 685 686 ``` 687 #include <bits/stdc++.h> 688 #define int long long 689 690 using namespace std; 691 692 const int lim = 893; 693 const int inf = 1e16; 694 695 struct dp_state 696 { 697 vector<int> a; 698 vector<int> b; 699 void init() 700 { 701 a.resize(lim + 1, inf); 702 b.resize(lim + 1, inf); 703 a[1] = 1; 704 b[1] = 2; 705 } 706 }; 707 708 int32_t main() 709 { 710 cin.tie(nullptr)->sync_with_stdio(false); 711 int q; 712 cin >> q; 713 while (q--) 714 { 715 int n; 716 cin >> n; 717 vector<vector<int>> g(n + 1); 718 vector<int> sz(n + 1); 719 720 for (int i = 1; i < n; ++i) 721 { 722 int x, y; 723 cin >> x >> y; 724 g[x].push_back(y); 725 g[y].push_back(x); 726 } 727 728 function<int(int, int)> shuffle_kids = [&](int node, int parent) 729 { 730 int sz = 1; 731 pair<int, int> best; 732 for (int i = 0; i < (int)g[node].size(); ++i) 733 { 734 if (g[node][i] != parent) 735 { 736 int sz2 = shuffle_kids(g[node][i], node); 737 738 best = max(best, {sz2, i}); 739 740 sz += sz2; 741 } 742 } 743 if (!g[node].empty()) 744 { 745 swap(g[node][0], g[node][best.second]); 746 } 747 return sz; 748 }; 749 shuffle_kids(1, 0); 750 751 vector<vector<int>> merged(2 * lim + 1, vector<int>(2, inf)); 752 753 function<dp_state(int, int)> dfs = [&](int node, int parent) 754 { 755 dp_state dp; 756 sz[node] = 1; 757 bool hasinit = false; 758 for (auto i : g[node]) 759 { 760 if (i != parent) 761 { 762 dp_state qui = dfs(i, node); 763 if (!hasinit) 764 { 765 dp.init(); 766 hasinit = true; 767 } 768 for (int j = 0; j <= min(sz[node], lim) + min(sz[i], lim); ++j) 769 { 770 merged[j][0] = merged[j][1] = inf; 771 } 772 for (int k = 1; k <= min(sz[node], lim); ++k) 773 { 774 for (int l = 1; l <= min(sz[i], lim); ++l) 775 { 776 merged[k][0] = min(merged[k][0], dp.a[k] + qui.b[l]); 777 merged[k][1] = min(merged[k][1], dp.b[k] + qui.a[l]); 778 merged[k + l][0] = min(merged[k + l][0], dp.a[k] + qui.a[l] + k * l); 779 merged[k + l][1] = min(merged[k + l][1], dp.b[k] + qui.b[l] + k * l * 2); 780 } 781 } 782 sz[node] += sz[i]; 783 for (int k = 1; k <= min(sz[node], lim); ++k) 784 { 785 dp.a[k] = merged[k][0]; 786 dp.b[k] = merged[k][1]; 787 } 788 } 789 } 790 if (!hasinit) 791 { 792 dp.init(); 793 hasinit = true; 794 } 795 return dp; 796 }; 797 dp_state dp = dfs(1, 0); 798 int ans = inf; 799 for (int i = 1; i <= lim; ++i) 800 { 801 ans = min(ans, dp.a[i]); 802 ans = min(ans, dp.b[i]); 803 } 804 cout << n * (n + 1) - ans << '\n'; 805 } 806 } 807 ``` 808 809 **Rate problem** 810 811 Good problem 812 813 Ok problem 814 815 Bad problem 816 817 Didn't solve it, idk 818 819 ## [1830E — Bully Sort](https://codeforces.com/contest/1830/problem/E) 820 821 Author: [cadmiumky](/profile/cadmiumky "Candidate Master cadmiumky") 822 823 Thanks to [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") for the solution! 824 825 **Solution** 826 827 First of all, we notice that if some element moves left, it will never move right. 828 829 **Proof** 830 831 Proving this is not hard, imagine $S$ to be the set of suffix minimas. Then if an element is in $S$ we know that $p_x \le x$. 832 833 Since after every bully swap an element cannot disappear from $S$ and after each bully swap, the $2$ swapped elements can only get closer to their desired position, we conclude the proof. 834 835 Obviously, if an element moves right, it will never move left since it will continue to move right until it reaches its final position. 836 837 By the $2$ claims above, we conclude that left and right movers are distinct. 838 839 Now suppose we swap indicies $i$ and $j$ and note that such swap kills $2 \cdot (j-i) - 1$ inversions and the left mover $j$ moves $j-i$ steps. 840 841 Now the magic is that if we let $s$ be the sum over $2 \cdot (i-p_i)$ for all left movers we have $s - ans = inversions$, thus our answer is just $s-inversions$. 842 843 Now to handle the data structure part, we just need to be able to calculate inversions while being able to perform point updates. There are many ways to do this, for example for using a fenwick tree and a bitwise trie/ordered_set in $O(nlog^2n)$. 844 845 **Code (tibinyte, fenwick tree + ordered_set C++)** 846 847 ``` 848 #include <bits/stdc++.h> 849 850 #include <ext/pb_ds/assoc_container.hpp> 851 852 #include <ext/pb_ds/tree_policy.hpp> 853 854 using namespace std; 855 856 using namespace __gnu_pbds; 857 858 #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 859 860 typedef long long ll; 861 862 /* .___ __ __ .__ 863 ____ ____ __| _/____ _______/ |______ ________/ |_ ______ | |__ ___________ ____ 864 _/ ___\/ _ \ / __ |/ __ \ / ___/\ __\__ \\_ __ \ __\/ ___/ | | \_/ __ \_ __ \_/ __ \ 865 \ \__( <_> ) /_/ \ ___/ \___ \ | | / __ \| | \/| | \___ \ | Y \ ___/| | \/\ ___/ 866 \___ >____/\____ |\___ > /____ > |__| (____ /__| |__| /____ > |___| /\___ >__| \___ > 867 \/ \/ \/ \/ \/ \/ \/ \/ \/ 868 */ 869 870 struct bit 871 { 872 int n; 873 vector<ordered_set> lesgo; 874 void resize(int _n) 875 { 876 n = _n; 877 lesgo = vector<ordered_set>(n + 1); 878 } 879 void update(int pos, int val, int sign) 880 { 881 for (int i = pos; i <= n; i += i & (-i)) 882 { 883 if (sign == -1) 884 { 885 lesgo[i].erase(val); 886 } 887 if (sign == 1) 888 { 889 lesgo[i].insert(val); 890 } 891 } 892 } 893 int query_smaller(int pos, int val) 894 { 895 int ans = 0; 896 for (int i = pos; i; i -= i & (-i)) 897 { 898 ans += lesgo[i].order_of_key(val); 899 } 900 return ans; 901 } 902 int query_greater(int pos, int val) 903 { 904 905 int ans = 0; 906 for (int i = pos; i; i -= i & (-i)) 907 { 908 int sz = lesgo[i].size(); 909 ans += sz - lesgo[i].order_of_key(val + 1); 910 } 911 return ans; 912 } 913 int query_smaller(int st, int dr, int val) 914 { 915 return query_smaller(dr, val) - query_smaller(st - 1, val); 916 } 917 int query_greater(int st, int dr, int val) 918 { 919 return query_greater(dr, val) - query_greater(st - 1, val); 920 } 921 }; 922 923 int32_t main() 924 { 925 cin.tie(nullptr)->sync_with_stdio(false); 926 int n, q; 927 cin >> n >> q; 928 vector<int> a(n + 1); 929 for (int i = 1; i <= n; ++i) 930 { 931 cin >> a[i]; 932 } 933 bit lesgo; 934 lesgo.resize(n); 935 for (int i = 1; i <= n; ++i) 936 { 937 lesgo.update(i, a[i], 1); 938 } 939 940 ll inv = 0; 941 942 for (int i = 1; i <= n; ++i) 943 { 944 inv += lesgo.query_greater(1, i, a[i]); 945 } 946 947 ll sum = 0; 948 949 for (int i = 1; i <= n; ++i) 950 { 951 sum += max(a[i] - i, 0); 952 } 953 954 while (q--) 955 { 956 int x, y; 957 cin >> x >> y; 958 if (x != y) 959 { 960 lesgo.update(x, a[x], -1); 961 lesgo.update(y, a[y], -1); 962 sum -= max(a[x] - x, 0); 963 sum -= max(a[y] - y, 0); 964 if (x + 1 <= y - 1) 965 { 966 int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]); 967 int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]); 968 inv += 2 * (y - x - 1 - lesgo1 - lesgo2); 969 } 970 971 if (a[x] > a[y]) 972 { 973 inv--; 974 } 975 else 976 { 977 inv++; 978 } 979 980 swap(a[x], a[y]); 981 sum += max(a[x] - x, 0); 982 sum += max(a[y] - y, 0); 983 lesgo.update(x, a[x], 1); 984 lesgo.update(y, a[y], 1); 985 } 986 cout << sum + sum - inv << '\n'; 987 } 988 } 989 ``` 990 991 **Code (tibinyte, sqrt decomposition, C++)** 992 993 ``` 994 #include <bits/stdc++.h> 995 996 using namespace std; 997 998 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 999 1000 int random(int st, int dr) 1001 { 1002 uniform_int_distribution<int> dist(st, dr); 1003 return dist(rng); 1004 } 1005 1006 typedef long long ll; 1007 1008 /* .___ __ __ .__ 1009 ____ ____ __| _/____ _______/ |______ ________/ |_ ______ | |__ ___________ ____ 1010 _/ ___\/ _ \ / __ |/ __ \ / ___/\ __\__ \\_ __ \ __\/ ___/ | | \_/ __ \_ __ \_/ __ \ 1011 \ \__( <_> ) /_/ \ ___/ \___ \ | | / __ \| | \/| | \___ \ | Y \ ___/| | \/\ ___/ 1012 \___ >____/\____ |\___ > /____ > |__| (____ /__| |__| /____ > |___| /\___ >__| \___ > 1013 \/ \/ \/ \/ \/ \/ \/ \/ \/ 1014 */ 1015 1016 struct decomp 1017 { 1018 vector<int> a; 1019 vector<pair<int, int>> buckets; 1020 vector<int> sp; 1021 vector<int> spbucket; 1022 vector<int> wh; 1023 const int sz = 400; 1024 void resize(int n) 1025 { 1026 a = vector<int>(n + 1); 1027 sp = vector<int>(n + 1); 1028 wh = vector<int>(n + 1); 1029 for (int i = 1; i <= n; i += sz) 1030 { 1031 int st = i; 1032 int dr = min(n, st + sz - 1); 1033 for (int j = st; j <= dr; ++j) 1034 { 1035 wh[j] = (int)buckets.size(); 1036 } 1037 buckets.push_back({st, dr}); 1038 spbucket.push_back(0); 1039 } 1040 } 1041 void update(int pos, int x) 1042 { 1043 a[pos] += x; 1044 int qui = wh[pos]; 1045 sp[buckets[qui].first] = a[buckets[qui].first]; 1046 for (int i = buckets[qui].first + 1; i <= buckets[qui].second; ++i) 1047 { 1048 sp[i] = sp[i - 1] + a[i]; 1049 } 1050 spbucket[0] = sp[buckets[0].second]; 1051 for (int i = 1; i < (int)buckets.size(); ++i) 1052 { 1053 spbucket[i] = spbucket[i - 1] + sp[buckets[i].second]; 1054 } 1055 } 1056 int query(int pos) 1057 { 1058 int qui = wh[pos]; 1059 int ans = sp[pos]; 1060 if (qui) 1061 { 1062 ans += spbucket[qui - 1]; 1063 } 1064 return ans; 1065 } 1066 }; 1067 1068 struct geralt 1069 { 1070 vector<int> a; 1071 vector<decomp> lesgo; 1072 vector<pair<int, int>> buckets; 1073 vector<int> wh; 1074 const int sz = 3000; 1075 void resize(int n) 1076 { 1077 a = vector<int>(n + 1); 1078 wh = vector<int>(n + 1); 1079 for (int i = 1; i <= n; i += sz) 1080 { 1081 int st = i; 1082 int dr = min(n, st + sz - 1); 1083 for (int j = st; j <= dr; ++j) 1084 { 1085 wh[j] = (int)buckets.size(); 1086 } 1087 buckets.push_back({st, dr}); 1088 lesgo.push_back({}); 1089 lesgo.back().resize(n); 1090 } 1091 } 1092 void update(int pos, int val) 1093 { 1094 int qui = wh[pos]; 1095 if (a[pos] != 0) 1096 { 1097 lesgo[qui].update(a[pos], -1); 1098 } 1099 a[pos] = val; 1100 lesgo[qui].update(a[pos], 1); 1101 } 1102 int query_brute(int st, int dr, int val) 1103 { 1104 int ans = 0; 1105 for (int i = st; i <= dr; ++i) 1106 { 1107 if (a[i] <= val) 1108 { 1109 ans++; 1110 } 1111 } 1112 return ans; 1113 } 1114 int query_smaller(int st, int dr, int val) // number of values <= val in st...dr 1115 { 1116 if (wh[st] == wh[dr]) 1117 { 1118 return query_brute(st, dr, val); 1119 } 1120 int qui1 = wh[st], qui2 = wh[dr]; 1121 int ans = query_brute(st, buckets[qui1].second, val) + query_brute(buckets[qui2].first, dr, val); 1122 qui1++; 1123 qui2--; 1124 for (int i = qui1; i <= qui2; ++i) 1125 { 1126 ans += lesgo[i].query(val); 1127 } 1128 return ans; 1129 } 1130 int query_greater(int st, int dr, int val) // number of values > val in st...dr 1131 { 1132 return (dr - st + 1) - query_smaller(st, dr, val); 1133 } 1134 }; 1135 1136 int32_t main() 1137 { 1138 cin.tie(nullptr)->sync_with_stdio(false); 1139 int n, q; 1140 cin >> n >> q; 1141 vector<int> a(n + 1); 1142 for (int i = 1; i <= n; ++i) 1143 { 1144 cin >> a[i]; 1145 } 1146 1147 geralt lesgo; 1148 lesgo.resize(n); 1149 1150 ll inv = 0; 1151 1152 for (int i = 1; i <= n; ++i) 1153 { 1154 lesgo.update(i, a[i]); 1155 inv += lesgo.query_greater(1, i, a[i]); 1156 } 1157 1158 ll sum = 0; 1159 1160 for (int i = 1; i <= n; ++i) 1161 { 1162 sum += max(a[i] - i, 0); 1163 } 1164 1165 while (q--) 1166 { 1167 int x, y; 1168 cin >> x >> y; 1169 if (x != y) 1170 { 1171 sum -= max(a[x] - x, 0); 1172 sum -= max(a[y] - y, 0); 1173 if (x + 1 <= y - 1) 1174 { 1175 int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]); 1176 int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]); 1177 inv += 2 * (y - x - 1 - lesgo1 - lesgo2); 1178 } 1179 1180 if (a[x] > a[y]) 1181 { 1182 inv--; 1183 } 1184 else 1185 { 1186 inv++; 1187 } 1188 1189 swap(a[x], a[y]); 1190 sum += max(a[x] - x, 0); 1191 sum += max(a[y] - y, 0); 1192 lesgo.update(x, a[x]); 1193 lesgo.update(y, a[y]); 1194 } 1195 cout << sum + sum - inv << '\n'; 1196 } 1197 } 1198 ``` 1199 1200 **Code (errorgorn, divide and conquer, C++)** 1201 1202 ``` 1203 #include <bits/stdc++.h> 1204 using namespace std; 1205 1206 #define ll long long 1207 #define ii pair<int,int> 1208 #define i4 tuple<int,int,int,int> 1209 #define fi first 1210 #define se second 1211 #define endl '\n' 1212 #define debug(x) cout << #x << ": " << x << endl 1213 1214 #define pub push_back 1215 #define pob pop_back 1216 #define puf push_front 1217 #define pof pop_front 1218 #define lb lower_bound 1219 #define ub upper_bound 1220 1221 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 1222 #define all(x) (x).begin(),(x).end() 1223 #define sz(x) (int)(x).size() 1224 1225 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1226 1227 struct FEN{ //we want to count the reverse 1228 int arr[500005]; 1229 1230 void update(int i,int k){ 1231 i=500005-i; 1232 1233 while (i<500005){ 1234 arr[i]+=k; 1235 i+=i&-i; 1236 } 1237 } 1238 1239 int query(int i){ 1240 i=500005-i; 1241 1242 int res=0; 1243 while (i){ 1244 res+=arr[i]; 1245 i-=i&-i; 1246 } 1247 return res; 1248 } 1249 } fen; 1250 1251 int n,q; 1252 int arr[500005]; 1253 long long ans[50005]; 1254 1255 void dnc(int l,int r,vector<i4> upd,vector<i4> que){ 1256 vector<i4> updl,updr; 1257 vector<i4> quel,quer; 1258 1259 int m=l+r>>1; 1260 1261 for (auto [a,b,c,d]:upd){ 1262 if (c<=m) updl.pub({a,b,c,d}); 1263 else updr.pub({a,b,c,d}); 1264 } 1265 1266 for (auto [a,b,c,d]:que){ 1267 if (c<=m) quel.pub({a,b,c,d}); 1268 else quer.pub({a,b,c,d}); 1269 } 1270 1271 int i=0; 1272 for (auto it:quer){ 1273 while (i<sz(updl) && get<0>(updl[i])<get<0>(it)){ 1274 fen.update(get<1>(updl[i]),get<3>(updl[i])); 1275 i++; 1276 } 1277 1278 ans[get<2>(it)]+=fen.query(get<1>(it))*get<3>(it); 1279 } 1280 while (i){ 1281 i--; 1282 fen.update(get<1>(updl[i]),-get<3>(updl[i])); 1283 } 1284 1285 if (l!=m) dnc(l,m,updl,quel); 1286 if (m+1!=r) dnc(m+1,r,updr,quer); 1287 } 1288 1289 signed main(){ 1290 ios::sync_with_stdio(0); 1291 cin.tie(0); 1292 cout.tie(0); 1293 cin.exceptions(ios::badbit | ios::failbit); 1294 1295 cin>>n>>q; 1296 rep(x,1,n+1) cin>>arr[x]; 1297 1298 vector<i4> upd,que; 1299 1300 rep(x,1,n+1) upd.pub({x,arr[x],-1,1}); 1301 rep(x,1,n+1) que.pub({x,arr[x],0,-1}); 1302 rep(x,1,n+1) ans[0]+=abs(x-arr[x]); 1303 1304 rep(x,1,q+1){ 1305 int a,b; 1306 cin>>a>>b; 1307 1308 if (a==b) continue; 1309 if (arr[a]<arr[b]) ans[x]--; 1310 else ans[x]++; 1311 1312 upd.pub({a,arr[a],x-1,-1}); 1313 upd.pub({b,arr[b],x-1,-1}); 1314 ans[x]-=abs(a-arr[a])+abs(b-arr[b]); 1315 1316 swap(arr[a],arr[b]); 1317 1318 upd.pub({a,arr[a],x,1}); 1319 upd.pub({b,arr[b],x,1}); 1320 ans[x]+=abs(a-arr[a])+abs(b-arr[b]); 1321 1322 que.pub({b,arr[b],x,-2}); 1323 que.pub({b,arr[a],x,2}); 1324 que.pub({a,arr[b],x,2}); 1325 que.pub({a,arr[a],x,-2}); 1326 1327 } 1328 1329 sort(all(upd)),sort(all(que)); 1330 1331 dnc(-1,q,upd,que); 1332 1333 rep(x,1,q+1) ans[x]+=ans[x-1]; 1334 rep(x,1,q+1) cout<<ans[x]<<" "; cout<<endl; 1335 } 1336 ``` 1337 1338 **Rate problem** 1339 1340 Good problem 1341 1342 Ok problem 1343 1344 Bad problem 1345 1346 Didn't solve it, idk 1347 1348 ## [1830F — The Third Grace](https://codeforces.com/contest/1830/problem/F) 1349 1350 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 1351 1352 Thanks to [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") for the editorial! 1353 1354 **Solution** 1355 1356 Let $dp_i$ be the maximum sum of costs of activated points that are $ \lt i$ over all states that has point $i$ activated. 1357 1358 When we transition from $dp_i$ to $dp_j$, we need to add the cost contributed by point $i$. The number of ranges where point $i$ is the largest coordinate within it are the ranges $[l,r]$ which satisfy $l \leq i \leq r \lt j$. So we have $dp_j = \max\limits_{i \lt j}(dp_i + p_i \cdot S_{i,j})$ where $S_{i,j}$ is the number of ranges $[l,r]$ which satisfy $l \leq i \leq r \lt j$. Now, we note that $S_{i,j} z$ 1359 1360 With some work, we can get calculate this $dp$ in $O(n^2)$. But this will be too slow, let's try to speed this up. 1361 1362 Let us define $dp_{i,j} = \max\limits_{k \leq i}(dp_k + p_k \cdot S_{k,j})$. We have $dp_{j-1,j}=dp_j$. Our goal is to go from (implictly) storing $dp_{i,i+1},dp_{i,i+2},\ldots,dp_{i,n}$ to $dp_{i+1,i+2},dp_{i+1,i+3},\ldots,dp_{i+1,n}$. As $dp_i + p_i \cdot S_{i,j}$ looks like a linear function w.r.t. $S_{i,j}$, we can try to use convex hull data structures to maintain it. 1363 1364 Let's figure out how $S_{i+1,j}$ relates to $S_{i,j}$. We need to subtract the number of ranges with $r=i$ and add the number of ranges with $l=i+1$ and $r \lt j$. This corresponds to $S_{i,*}$ and $S_{i+1,*}$ differing by amortized $O(1)$ suffix increment updates. Also, note that $S_{i,*}$ is non-decreasing. 1365 1366 So we want to support the following data structure: Initially we have an arrays $A$ and $X$ that are both initially $0$. Handle the following updates: 1367 1368 * `1 m c` $A_i \gets \max(A_i,m \cdot X_i + c)$ for all $i$ 1369 * `2 j k` $X_i \gets X_i + k$ for all $j \leq i$. It is guaranteed that $X$ will always be non-decreasing. 1370 * `3 i` find $A_i$ 1371 1372 This can be maintained in a lichao tree in $O(log ^2)$ time. In each lichao node, we need to store $s,m,e$, the start, middle and end indices and their corresponding $X$ values $X_s,X_m,X_e$ respectively. This way, we can support operations $1$ and $3$ already. 1373 1374 To support operation $2$, note that in a lichao tree, you can use $O(log^2)$ time to push down all lines that covers a certain point (refer to <https://codeforces.com/blog/entry/86731)>. This way, all lines in the li chao tree are in $[1,j)$ or $[j,n]$, so you can do lazy updates on both the coordinates of the lines and the $X$ values. 1375 1376 The time complexity is $O(n \log^2)$. 1377 1378 There is another solution that works in $O(m \log^3)$ that we are unable to optimize further yet. Let us flip the array so that the condition is on the activated point with the smallest coordinate. Then we have $dp_j = \max\limits_{i \lt j}(dp_i + p_j \cdot S_{i,j})$ where $S_{i,j}$ counts the number of ranges $[l,r]$ such that $i \lt l \leq j \leq r$. 1379 1380 Now, we want to store the linear function $dp_i + x \cdot S_{i,j}$ in some sort of data structure so that we can evaluate the maximum value with $x=p_j$. Unfortunately, the value of $S_{i,j}$ can change by suffix additions, similar to above. 1381 1382 But since $S_{i,j}$ is non-increasing here, that means the optimal $i$ that maximizes $dp_i + x \cdot S_{i,j}$ decreases when $x$ increases. That is, for $l_1 \leq r_1 \lt l_2 \leq r_2$ and we have two data structures that can get the maximum $f_j(x)=dp_i+x \cdot S_{i,j}$ for $l_j \leq i \leq r_j$ respectively. We can combine these $2$ data structures to make it for $[l_1,r_1] \cup [l_2,r_2]$ by binary searching the point $X$ where for all $x \leq X$, $f_1(x) \leq f_2(x)$ and for all $X \leq x,f_1(x) \geq f_2(x)$. Since querying this data structure takes $O(\log n)$, it takes $O(\log ^2)$ time to combine two such data structures. If we use a segment tree, we only need to rebuild $O(\log^3)$ different data structures (the rest can be handled using lazy tags), giving us a time complexity of $O(\log^3)$. 1383 1384 **Code (errorgorn, C++)** 1385 1386 ``` 1387 //もう布団の中から出たくない 1388 //布団の外は寒すぎるから 1389 //布団の中から出たくない 1390 //布団の中はあたたかすぎるから 1391 1392 #include <bits/stdc++.h> 1393 using namespace std; 1394 1395 #pragma GCC optimize("O3,unroll-loops") 1396 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 1397 1398 #define int long long 1399 #define ll long long 1400 #define ii pair<ll,ll> 1401 #define iii pair<ii,ll> 1402 #define fi first 1403 #define se second 1404 #define endl '\n' 1405 #define debug(x) cout << #x << ": " << x << endl 1406 1407 #define pub push_back 1408 #define pob pop_back 1409 #define puf push_front 1410 #define pof pop_front 1411 #define lb lower_bound 1412 #define ub upper_bound 1413 1414 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 1415 #define all(x) (x).begin(),(x).end() 1416 #define sz(x) (int)(x).size() 1417 1418 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1419 1420 const ll INF=1e18; 1421 1422 struct line{ 1423 ll m,c; 1424 1425 line (ll _m,ll _c){ 1426 m=_m,c=_c; 1427 } 1428 1429 ll get(ll x){ 1430 return m*x+c; 1431 } 1432 }; 1433 1434 struct node{ 1435 int s,e,m; 1436 int vs=0,ve=0,vm=0; 1437 line val={0,-INF}; 1438 int lazy=0; 1439 node *l,*r; 1440 1441 node(int _s,int _e){ 1442 s=_s,e=_e,m=s+e>>1; 1443 1444 if (s!=e){ 1445 l=new node(s,m); 1446 r=new node(m+1,e); 1447 } 1448 } 1449 1450 void propo(){ 1451 if (lazy==0) return; 1452 1453 val.c-=val.m*lazy; 1454 vs+=lazy; 1455 ve+=lazy; 1456 vm+=lazy; 1457 1458 if (s!=e){ 1459 l->lazy+=lazy; 1460 r->lazy+=lazy; 1461 } 1462 lazy=0; 1463 } 1464 1465 void update(int i){ 1466 if (s==i) lazy++; 1467 else{ 1468 if (val.c!=-INF){ 1469 l->propo(),r->propo(); 1470 l->update(val),r->update(val); 1471 val={0,-INF}; 1472 } 1473 1474 if (m<i) r->update(i); 1475 else l->update(i),r->update(m+1); 1476 1477 l->propo(),r->propo(); 1478 vs=l->vs,vm=l->ve,ve=r->ve; 1479 } 1480 } 1481 1482 void update(line i){ 1483 bool lo=i.get(vs)>val.get(vs); 1484 bool mi=i.get(vm)>val.get(vm); 1485 bool hi=i.get(ve)>val.get(ve); 1486 1487 if (mi) swap(i,val); 1488 1489 if (s==e || i.c==-INF || lo==hi) return; 1490 1491 l->propo(),r->propo(); 1492 if (lo!=mi) l->update(i); 1493 else r->update(i); 1494 } 1495 1496 ii query(ll i){ 1497 propo(); 1498 1499 if (s==e) return {val.get(vs),vs}; 1500 else if (i<=m){ 1501 auto temp=l->query(i); 1502 return {max(temp.fi,val.get(temp.se)),temp.se}; 1503 } 1504 else{ 1505 auto temp=r->query(i); 1506 return {max(temp.fi,val.get(temp.se)),temp.se}; 1507 } 1508 } 1509 } *root; 1510 1511 const int maxn = 1e6; 1512 const int maxm = 1e6; 1513 1514 int n,m; 1515 ii arr[maxn+1]; 1516 ii brr[maxm+1]; 1517 1518 int ans[maxm+1]; 1519 1520 signed main(){ 1521 ios::sync_with_stdio(0); 1522 cin.tie(0); 1523 cout.tie(0); 1524 cin.exceptions(ios::badbit | ios::failbit); 1525 1526 int TC; 1527 cin>>TC; 1528 while (TC--){ 1529 cin>>n>>m; 1530 rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se; 1531 rep(x,1,m+1){ 1532 cin>>brr[x].se; 1533 brr[x].fi = x; 1534 } 1535 1536 sort(arr+1,arr+n+1); 1537 1538 root=new node(0,m+1); 1539 root->update({0,0}); 1540 1541 int curr=1; 1542 rep(x,0,m+2){ 1543 while (curr<=n && arr[curr].fi==x) root->update(arr[curr++].se+1); 1544 auto temp=root->query(x); 1545 root->update({brr[x].se,temp.fi-brr[x].se*temp.se}); 1546 } 1547 1548 cout<<root->query(m+1).fi<<endl; 1549 } 1550 } 1551 ``` 1552 1553 **Code (valeriu, C++)** 1554 1555 ``` 1556 #include <bits/stdc++.h> 1557 #define all(x) (x).begin(),(x).end() 1558 using namespace std; 1559 1560 using ll = long long; 1561 using ld = long double; 1562 1563 //#define int ll 1564 #define sz(x) ((int)(x).size()) 1565 1566 using pii = pair<ll,ll>; 1567 using tii = tuple<int,int,int>; 1568 1569 const int nmax = 5e5 + 5, qmax = 2e6 + 5; 1570 const ll inf = 1e18 + 5; 1571 1572 struct line { 1573 ll m = 0, b = -inf; 1574 ll operator()(const ll& x) const { 1575 return m * x + b; 1576 } 1577 bool operator ==(const line& x) const { return m == x.m && b == x.b; } 1578 }; 1579 1580 int M; 1581 1582 namespace AINT { 1583 struct Node { 1584 int vl = 0, vmid = 0, vr = 0; 1585 line val = line{0, -inf}; 1586 Node() {;} 1587 void operator += (const int &x) { vl += x, vmid += x, vr += x; val.b -= val.m * x; } 1588 } aint[qmax * 4]; 1589 int lazy[qmax * 4]; 1590 1591 void push(int node) { 1592 lazy[2 * node] += lazy[node]; 1593 aint[2 * node] += lazy[node]; 1594 lazy[2 * node + 1] += lazy[node]; 1595 aint[2 * node + 1] += lazy[node]; 1596 lazy[node] = 0; 1597 } 1598 void pushline(line x, int node = 1, int cl = 0, int cr = M) { 1599 bool l = x(aint[node].vl) > aint[node].val(aint[node].vl), m = x(aint[node].vmid) > aint[node].val(aint[node].vmid), r = x(aint[node].vr) > aint[node].val(aint[node].vr); 1600 if(m) swap(x, aint[node].val); 1601 if(cl == cr || x == line() || l == r) return; 1602 1603 int mid = cl + cr >> 1; 1604 push(node); 1605 if(m != l) pushline(x, 2 * node, cl, mid); 1606 else pushline(x, 2 * node + 1, mid + 1, cr); 1607 return; 1608 } 1609 void add(int l, int node = 1, int cl = 0, int cr = M) { 1610 if(cl >= l) { 1611 lazy[node]++; 1612 aint[node] += 1; 1613 return; 1614 } 1615 if(cr < l) return; 1616 int mid = cl + cr >> 1; 1617 1618 push(node); 1619 1620 pushline(aint[node].val, 2 * node, cl, mid); 1621 pushline(aint[node].val, 2 * node + 1, mid + 1, cr); 1622 aint[node].val = line{0, -inf}; 1623 1624 add(l, 2 * node, cl, mid); 1625 add(l, 2 * node + 1, mid + 1, cr); 1626 aint[node].vl = aint[2 * node].vl; 1627 aint[node].vmid = aint[2 * node].vr; 1628 aint[node].vr = aint[2 * node + 1].vr; 1629 } 1630 pii query(ll p, int node = 1, int cl = 0, int cr = M) { 1631 if(cl == cr) return pii{aint[node].val(aint[node].vl), aint[node].vl}; 1632 int mid = cl + cr >> 1; 1633 push(node); 1634 auto [mxv, atrv] = p <= mid? query(p, 2 * node, cl, mid) : query(p, 2 * node + 1, mid + 1, cr); 1635 return pii{max(mxv, aint[node].val(atrv)), atrv}; 1636 } 1637 1638 void init(int node = 1, int cl = 0, int cr = M) { 1639 aint[node] = Node(); 1640 lazy[node] = 0; 1641 if(cl == cr) return; 1642 int mid = cl + cr >> 1; 1643 init(2 * node, cl, mid); 1644 init(2 * node + 1, mid + 1, cr); 1645 return; 1646 } 1647 }; 1648 1649 vector<int> atraddp[qmax]; 1650 ll val[qmax]; 1651 1652 void testcase() { 1653 int n, m; 1654 cin >> n >> m; 1655 M = m + 2; 1656 for(int i = 0, l, r; i < n; i++) { 1657 cin >> l >> r; 1658 atraddp[l].emplace_back(r + 1); 1659 } 1660 for(int i = 1; i <= m; i++) 1661 cin >> val[i]; 1662 1663 AINT::init(); 1664 AINT::pushline({0, 0}); 1665 1666 for(int i = 0; i < m + 2; i++) { 1667 for(auto x : atraddp[i]) 1668 AINT::add(x); 1669 auto [a, b] = AINT::query(i); 1670 //cerr << a << ' ' << b << '\n'; 1671 AINT::pushline({val[i], a - val[i] * b}); 1672 } 1673 1674 for(int i = 0; i < m + 2; i++) 1675 atraddp[i].clear(); 1676 1677 cout << AINT::query(m + 1).first << '\n'; 1678 } 1679 1680 signed main() { 1681 cin.tie(0) -> sync_with_stdio(0); 1682 int t; 1683 cin >> t; 1684 while(t--) testcase(); 1685 1686 } 1687 1688 /** 1689 Anul asta se da centroid. 1690 -- Surse oficiale 1691 */ 1692 ``` 1693 1694 **Rate problem** 1695 1696 Good problem 1697 1698 Ok problem 1699 1700 Bad problem 1701 1702 Didn't solve it, idk 1703 1704 If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments.