1869.md (42022B)
1 Source: https://codeforces.com/blog/entry/116642 2 3 [1869A - Make It Zero](/contest/1869/problem/A "Codeforces Round 896 (Div. 2)") 4 5 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan") 6 7 **Hint 1** 8 9 Indeed at most $\bf 4$ operations will be used. 10 11 **Hint 2** 12 13 If $r-l+1$ is even, and you do the operation on $[l,r]$ twice, then the subarray $a[l;r]$ will all become $0$. 14 15 **Solution** 16 17 Tutorial is loading... 18 19 **Implementation** 20 21 ``` 22 #include <bits/stdc++.h> 23 #define all(s) s.begin(), s.end() 24 using namespace std; 25 using ll = long long; 26 using ull = unsigned long long; 27 28 const int _N = 1e5 + 5; 29 30 int T; 31 32 void solve() { 33 int n; cin >> n; 34 vector<int> a(n); 35 for (int i = 0; i < n; i++) cin >> a[i]; 36 if (n & 1) { 37 cout << "4" << '\n'; 38 cout << "1 " << n - 1 << '\n'; 39 cout << "1 " << n - 1 << '\n'; 40 cout << n - 1 << ' ' << n << '\n'; 41 cout << n - 1 << ' ' << n << '\n'; 42 } else { 43 cout << "2" << '\n'; 44 cout << "1 " << n << '\n'; 45 cout << "1 " << n << '\n'; 46 } 47 return; 48 } 49 50 int main() { 51 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 52 cin >> T; 53 while (T--) { 54 solve(); 55 } 56 } 57 ``` 58 59 **Rate the problem** 60 61 * Amazing problem: 62 * Good problem: 63 * Average problem: 64 * Bad problem: 65 * Didn't solve: 66 67 [1869B - 2D Traveling](/contest/1869/problem/B "Codeforces Round 896 (Div. 2)") 68 69 Author: [programpiggy](/profile/programpiggy "Expert programpiggy") 70 71 **Hint** 72 73 What will happen if there are no major cities? 74 75 **Solution** 76 77 Tutorial is loading... 78 79 **Implementation** 80 81 ``` 82 #include <bits/stdc++.h> 83 #define all(s) s.begin(), s.end() 84 using namespace std; 85 using ll = long long; 86 using ull = unsigned long long; 87 88 const int _N = 1e5 + 5; 89 90 int T; 91 92 void solve() { 93 int n, k, s, t; cin >> n >> k >> s >> t; 94 vector<int> x(n + 1), y(n + 1); 95 for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; 96 ll ans = llabs(x[s] - x[t]) + llabs(y[s] - y[t]); 97 ll mins = LLONG_MAX / 2, mint = LLONG_MAX / 2; 98 for (int i = 1; i <= k; i++) { 99 mins = min(mins, llabs(x[s] - x[i]) + llabs(y[s] - y[i])); 100 mint = min(mint, llabs(x[t] - x[i]) + llabs(y[t] - y[i])); 101 } 102 ans = min(ans, mins + mint); 103 cout << ans << '\n'; 104 return; 105 } 106 107 int main() { 108 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 109 cin >> T; 110 while (T--) { 111 solve(); 112 } 113 } 114 ``` 115 116 **Rate the problem** 117 118 * Amazing problem: 119 * Good problem: 120 * Average problem: 121 * Bad problem: 122 * Didn't solve: 123 124 [1868A - Fill in the Matrix](/contest/1868/problem/A "Codeforces Round 896 (Div. 1)") 125 126 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan") 127 128 **Hint 1** 129 130 What is the upper bound of $s$ according to $n$ and $m$? Can you construct such a matrix that reaches the upper bound? 131 132 **Hint 2** 133 134 If not, can you construct a matrix which maximizes $\sum_{i=1}^m v_i$? This is of some help to get the solution. 135 136 **Solution** 137 138 Tutorial is loading... 139 140 **Implementation** 141 142 ``` 143 #include <bits/stdc++.h> 144 #define all(s) s.begin(), s.end() 145 using namespace std; 146 using ll = long long; 147 using ull = unsigned long long; 148 149 const int _N = 1e5 + 5; 150 151 int T; 152 153 void solve() { 154 int n, m; 155 cin >> n >> m; 156 if (m == 1) cout << 0 << '\n'; 157 else if (n > m - 1) cout << m << '\n'; 158 else cout << n + 1 << '\n'; 159 for (int i = 0; i < min(m - 1, n); i++) { 160 for (int j = 0; j < m; j++) { 161 cout << (j + i) % m << ' '; 162 } 163 cout << '\n'; 164 } 165 if (n > m - 1) { 166 for (int i = m - 1; i < n; i++) { 167 for (int j = 0; j < m; j++) { 168 cout << j << ' '; 169 } 170 cout << '\n'; 171 } 172 } 173 return; 174 } 175 176 int main() { 177 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 178 cin >> T; 179 while (T--) { 180 solve(); 181 } 182 } 183 ``` 184 185 **Rate the problem** 186 187 * Amazing problem: 188 * Good problem: 189 * Average problem: 190 * Bad problem: 191 * Didn't solve: 192 193 [1868B1 - Candy Party (Easy Version)](/contest/1868/problem/B1 "Codeforces Round 896 (Div. 1)") 194 195 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan") 196 197 **Hint 1** 198 199 You can calculate the number of candies of each person after the swap easily. Denote the number as $s$. 200 201 **Hint 2** 202 203 Since a person gives candies to and receives candies from exactly one person, assume he gives away $2^x$ candies and receives $2^y$ candies, then we have $a_i - 2^x + 2^y = s$. If $a_i \ne s$, at most how many pairs $(x,y)$ can satisfy this equation? 204 205 **Hint 3** 206 207 Do the two restrictions in the statement, 208 209 > Note that one cannot give more candies than currently he has (he might receive candies from someone else before) and he cannot give candies to himself, either. 210 211 really make any difference to the answer? 212 213 **Solution** 214 215 Tutorial is loading... 216 217 **Implementation** 218 219 ``` 220 #include <bits/stdc++.h> 221 #define all(s) s.begin(), s.end() 222 using namespace std; 223 using ll = long long; 224 using ull = unsigned long long; 225 226 const int _N = 1e5 + 5; 227 228 int T; 229 230 void solve() { 231 int n; cin >> n; 232 vector<ll> a(n); ll sum = 0; 233 for (int i = 0; i < n; i++) cin >> a[i], sum += a[i]; 234 if (sum % n) return cout << "No" << '\n', void(); 235 sum /= n; 236 vector<int> bit(31, 0); 237 auto lowbit = [](int x) { 238 return x & (-x); 239 }; 240 for (int i = 0; i < n; i++) { 241 if (a[i] == sum) continue; 242 int d = abs(a[i] - sum); 243 int p = lowbit(d); 244 int e = d + p; 245 if (__builtin_popcount(e) == 1) { 246 if (a[i] > sum) bit[__lg(e)]++, bit[__lg(p)]--; 247 else bit[__lg(e)]--, bit[__lg(p)]++; 248 } else { 249 cout << "No" << '\n'; 250 return; 251 } 252 } 253 for (int i = 0; i < 31; i++) { 254 if (bit[i]) { 255 cout << "No" << '\n'; 256 return; 257 } 258 } 259 cout << "Yes" << '\n'; 260 return; 261 } 262 263 int main() { 264 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 265 cin >> T; 266 while (T--) { 267 solve(); 268 } 269 } 270 ``` 271 272 **Rate the problem** 273 274 * Amazing problem: 275 * Good problem: 276 * Average problem: 277 * Bad problem: 278 * Didn't solve: 279 280 [1868B2 - Candy Party (Hard Version)](/contest/1868/problem/B2 "Codeforces Round 896 (Div. 1)") 281 282 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan") 283 Please, read the tutorial for B1 first. 284 285 **Hint 4** 286 287 For whom may not give or receive candies? 288 289 **Hint 5** 290 291 When $|a_i-s|$ is a power of $2$, how many ways can the person gives/receives candies at most? 292 293 **Hint 6** 294 295 Try to determine some people's way to give/receive candies first, then others. 296 297 **How to do this?** 298 299 Bit-by-bit. 300 301 **Solution** 302 303 Tutorial is loading... 304 305 **Implementation** 306 307 ``` 308 #include <bits/stdc++.h> 309 #define all(s) s.begin(), s.end() 310 using namespace std; 311 using ll = long long; 312 using ull = unsigned long long; 313 314 const int _N = 1e5 + 5; 315 316 int T; 317 318 void solve() { 319 int n; cin >> n; 320 vector<ll> a(n); ll sum = 0; 321 for (int i = 0; i < n; i++) cin >> a[i], sum += a[i]; 322 if (sum % n) return cout << "No" << '\n', void(); 323 sum /= n; 324 vector<int> bit(31, 0), pow1(31, 0), pow2(31, 0); 325 for (int i = 0; i < n; i++) { 326 int flag = 0; 327 if (a[i] == sum) continue; 328 for (int j = 0; j < 31; j++) { 329 if (a[i] + (1 << j) == sum) { 330 pow1[j]++; 331 flag = 1; 332 continue; 333 } 334 if (a[i] - (1 << j) == sum) { 335 pow2[j]++; 336 flag = 1; 337 continue; 338 } 339 } 340 if (flag) continue; 341 flag = 0; 342 for (int j = 0; j < 31; j++) { 343 for (int k = 0; k < 31; k++) { 344 if (a[i] + (1 << j) - (1 << k) == sum) { 345 flag = 1; 346 bit[j]++; 347 bit[k]--; 348 } 349 } 350 } 351 if (!flag) { 352 cout << "No" << '\n'; 353 return; 354 } 355 } 356 for (int i = 30; i >= 0; i--) { 357 bit[i] += (pow1[i] - pow2[i]); 358 if (i == 0) break; 359 if (bit[i] < 0) { 360 pow1[i - 1] -= -bit[i]; 361 bit[i - 1] -= -bit[i]; 362 if (pow1[i - 1] < 0) { 363 cout << "No" << '\n'; 364 return; 365 } 366 } else { 367 pow2[i - 1] -= bit[i]; 368 bit[i - 1] += bit[i]; 369 if (pow2[i - 1] < 0) { 370 cout << "No" << '\n'; 371 return; 372 } 373 } 374 } 375 if (bit[0] == 0) cout << "Yes" << '\n'; 376 else cout << "No" << '\n'; 377 return; 378 } 379 380 int main() { 381 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 382 cin >> T; 383 while (T--) { 384 solve(); 385 } 386 } 387 ``` 388 389 **Rate the problem** 390 391 * Amazing problem: 392 * Good problem: 393 * Average problem: 394 * Bad problem: 395 * Didn't solve: 396 397 [1868C - Travel Plan](/contest/1868/problem/C "Codeforces Round 896 (Div. 1)") 398 399 Author: [programpiggy](/profile/programpiggy "Expert programpiggy") 400 401 **Hint 1** 402 403 For any simple path length $t$, what's the sum of the maximum value of cities in all assignments? For the cities out of the path, their value doesn't matter. 404 405 **Hint 2** 406 407 Consider an easy dp to calculate the number of paths with different lengths. 408 409 **Hint 3** 410 411 How many different subtrees are there in this tree? 412 413 **Hint 4** 414 415 What's the maximum length of the paths? 416 417 **Hint 5** 418 419 Try to optimize the dp with the conclusion you get in Hint 3 and Hint 4. 420 421 **Solution** 422 423 Tutorial is loading... 424 425 $\mathcal O(\sum(m\log n+\log^3n))$ solution by [programpiggy](/profile/programpiggy "Expert programpiggy"): 426 427 **Implementation** 428 429 ``` 430 #include <bits/stdc++.h> 431 #define ll long long 432 #define ull unsigned long long 433 using namespace std; 434 #pragma GCC optimize("Ofast") 435 436 ll tot[505],n,m,dp[125][125],dp2[125],g[125][125],g2[125],f[125],pw[100005][125]; 437 const ll mod=998244353; 438 439 inline ll dep( ll root) { 440 if (root>n)return 0; 441 return dep(root*2)+1; 442 } 443 444 inline ll dep2( ll root) { 445 if (root>n)return 0; 446 return dep2(root*2+1)+1; 447 } 448 449 inline bool full( ll root) { 450 return dep(root)==dep2(root); 451 } 452 453 void dfs( ll root) { 454 if (root*2>n) { 455 g2[0]=dp2[0]=1; 456 return; 457 } 458 if (root*2==n) { 459 g2[0]=2,g2[1]=1; 460 dp2[0]=1,dp2[1]=1; 461 return; 462 } 463 ll d=0; 464 if (full(root*2)) { 465 466 d=dep(root*2); 467 dfs(root*2+1); 468 } else { 469 d=dep(root*2+1); 470 dfs(root*2); 471 } 472 ll mx=2*d+4; 473 for (ll i=0; i<=mx; i++) { 474 g2[i]+=g[d][i]; 475 for (ll j=0; j<=min(d+2,i); j++) { 476 g2[i+2]+=dp2[j]*dp[d][i-j]%mod; 477 } 478 } 479 for (ll i=mx; i>0; i--)dp2[i]=(dp2[i-1]+dp[d][i-1])%mod; 480 dp2[0]=1; 481 for (ll i=0; i<=mx; i++)g2[i]+=dp2[i],g2[i]%=mod; 482 } 483 484 inline ll qkp(ll a,ll k) { 485 ll ans=1; 486 while (k) { 487 if (k&1)ans*=a,ans%=mod; 488 a*=a,a%=mod; 489 k>>=1; 490 } 491 return ans; 492 } 493 494 int main() { 495 ll t; 496 scanf("%lld",&t); 497 for (ll i=1; i<=60; i++) { 498 dp[i][0]=1; 499 for (ll j=1; j<=i-1; j++) { 500 dp[i][j]=2*dp[i-1][j-1]%mod; 501 } 502 for (ll j=0; j<=2*i-2; j++) { 503 g[i][j]+=g[i-1][j]*2; 504 g[i][j]+=dp[i][j]; 505 g[i][j]%=mod; 506 for (ll k=0; k<=j; k++) { 507 g[i][j+2]+=dp[i-1][k]*dp[i-1][j-k]%mod; 508 g[i][j+2]%=mod; 509 } 510 } 511 } 512 while (t--) { 513 scanf("%lld%lld",&n,&m); 514 515 // log n^3 516 dfs(1); 517 ll d=dep(1),ans=0; 518 for (ll j=0; j<=m; j++) { 519 pw[j][0]=1; 520 for (ll i=1; i<=2*d; i++) { 521 pw[j][i]=pw[j][i-1]*j%mod; 522 } 523 } 524 525 for (ll i=0; i<=2*d-2; i++) { 526 for (ll j=1; j<=m; j++) { 527 f[i]+=(pw[j][i+2]+mod-pw[j-1][i+1]*j%mod)%mod; 528 f[i]%=mod; 529 } 530 if (n>=i+1) 531 ans+=f[i]*g2[i]%mod*qkp(m,n-i-1)%mod; 532 ans%=mod; 533 } 534 printf("%lld\n",ans); 535 for (ll i=1;i<=60;i++){ 536 for (ll j=0;j<=2*i-2;j++){ 537 f[j]=g2[j]=dp2[j]=0; 538 } 539 } 540 } 541 542 return 0; 543 } 544 ``` 545 546 $\mathcal O(\sum \log^3n)$ solution by [sszcdjr](/profile/sszcdjr "Master sszcdjr"): 547 548 **Implementation** 549 550 ``` 551 #include <bits/stdc++.h> 552 #define int long long 553 #define double long double 554 #define mid ((l+r)>>1) 555 using namespace std; 556 const int mod=998244353; 557 int qp(int a,int b){ 558 int ans=1; 559 while(b){ 560 if(b&1) ans=(ans*a)%mod; 561 a=(a*a)%mod; 562 b>>=1; 563 } 564 return ans; 565 } 566 int fac[1000005],inv[1000005]; 567 void init(){ 568 fac[0]=1; 569 for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod; 570 inv[1000000]=qp(fac[1000000],mod-2); 571 for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; 572 } 573 int C(int i,int j){ 574 if(i<0||j<0||i<j) return 0; 575 return fac[i]*inv[i-j]%mod*inv[j]%mod; 576 } 577 int cnt=0; 578 int reg[100005][131],reg2[100005][131]; 579 unordered_map<int,int> mp; 580 void dfs(int now){ 581 if(mp[now]) return ; 582 mp[now]=++cnt; 583 if(now==0) return ; 584 reg[cnt][0]++,reg2[cnt][0]++; 585 if(now==1) return ; 586 int i=0; 587 for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break; 588 i-=2; 589 int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1; 590 if(lft<=(1LL<<i)) lnum+=lft; 591 else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i)); 592 dfs(lnum),dfs(rnum); 593 int ml=mp[lnum],mr=mp[rnum],mn=mp[now]; 594 for(int i=0;i<=130;i++){ 595 for(int j=0;j<=130;j++){ 596 if(i+j+2>=130) break; 597 (reg2[mn][i+j+2]+=(reg[ml][i]*reg[mr][j]))%=mod; 598 } 599 } 600 for(int i=0;i<=129;i++) (reg[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i]+=reg2[ml][i]+reg2[mr][i])%=mod; 601 } 602 int pw[100005][150],tot[205]; 603 signed main(){ 604 init(); 605 int t; cin>>t; 606 while(t--){ 607 int n,m; 608 cin>>n>>m; 609 dfs(n); 610 int nn=mp[n]; 611 int ans=0; 612 tot[0]=(m-1)%mod; 613 for(int i=2;i<=135;i++){ 614 tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod; 615 for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod; 616 (tot[i-1]*=qp(i,mod-2))%=mod; 617 } 618 for(int i=0;i<=min(130ll,n-1);i++){ 619 int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod; 620 (ans+=tmp*reg2[nn][i]%mod*qp(m%mod,n-(i+1)))%=mod; 621 } 622 cout<<ans<<"\n"; 623 } 624 return 0; 625 } 626 ``` 627 628 $\mathcal O(\sum \log^2n)$ solution by [sszcdjr](/profile/sszcdjr "Master sszcdjr"): 629 630 **Implementation** 631 632 ``` 633 #include <bits/stdc++.h> 634 #define int long long 635 #define double long double 636 #define mid ((l+r)>>1) 637 using namespace std; 638 const int mod=998244353; 639 int qp(int a,int b){ 640 int ans=1; 641 while(b){ 642 if(b&1) ans=(ans*a)%mod; 643 a=(a*a)%mod; 644 b>>=1; 645 } 646 return ans; 647 } 648 int fac[1000005],inv[1000005]; 649 void init(){ 650 fac[0]=1; 651 for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod; 652 inv[1000000]=qp(fac[1000000],mod-2); 653 for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; 654 } 655 int C(int i,int j){ 656 if(i<0||j<0||i<j) return 0; 657 return fac[i]*inv[i-j]%mod*inv[j]%mod; 658 } 659 int cnt=0; 660 int reg[100005][131],dep[100005],depc[100005],rett[131],invi[131]; 661 unordered_map<int,int> mp; 662 void dfs(int now){ 663 if(mp[now]) return ; 664 mp[now]=++cnt; 665 if(now==0) return ; 666 dep[cnt]=1,depc[cnt]=1,reg[cnt][0]++; 667 if(now==1) return ; 668 int i=0; 669 for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break; 670 i-=2; 671 int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1; 672 if(lft<=(1LL<<i)) lnum+=lft; 673 else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i)); 674 dfs(lnum),dfs(rnum); 675 int ml=mp[lnum],mr=mp[rnum],mn=mp[now]; 676 if(dep[ml]>dep[mr]){ 677 dep[mn]=dep[ml]+1; depc[mn]=depc[ml]; 678 for(int i=0;i<=129;i++) reg[mn][i]=reg[ml][i]; 679 } 680 else{ 681 dep[mn]=dep[ml]+1; depc[mn]=(depc[ml]+depc[mr])%mod; 682 for(int i=0;i<=129;i++) reg[mn][i]=(reg[ml][i]+reg[mr][i])%mod; 683 (reg[mn][dep[mn]*2-2]+=depc[ml]*depc[mr])%=mod; 684 } 685 } 686 int pw[100005][150],tot[205],pw2[135]; 687 signed main(){ 688 pw2[0]=1; 689 for(int i=1;i<=130;i++) pw2[i]=pw2[i-1]*2%mod,invi[i]=qp(i,mod-2); 690 init(); 691 int t; cin>>t; 692 while(t--){ 693 int n,m; 694 cin>>n>>m; 695 int lg=0,lft; 696 for(int i=0;i<=130;i++) rett[i]=0; 697 for(lg=61;lg>=0;lg--){ 698 if(n>=(1LL<<(lg+1))-1){ 699 lft=n-((1LL<<(lg+1))-1); 700 lft%=mod; 701 break; 702 } 703 } 704 for(int i=0;i<=lg;i++){ 705 for(int j=0;j<=lg;j++){ 706 int tt=max(i,j); 707 (rett[i+j]+=(pw2[lg-tt+1]-1)*pw2[max(0ll,i-1)+max(0ll,j-1)]%mod)%=mod; 708 } 709 } 710 for(int i=1;i<=lg+1;i++){ 711 for(int j=0;j<i;j++){ 712 (rett[i+j]+=lft*pw2[max(0ll,j-1)]%mod)%=mod; 713 } 714 } 715 dfs(n); 716 int nn=mp[n]; 717 if(n!=(1ll<<(lg+1))-1) for(int i=0;i<=130;i++) (rett[i]+=reg[nn][i])%=mod; 718 int ans=0; 719 tot[0]=(m-1)%mod; 720 for(int i=2;i<=130;i++){ 721 tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod; 722 for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod; 723 (tot[i-1]*=invi[i])%=mod; 724 } 725 for(int i=0;i<=min(130ll,n-1);i++){ 726 int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod; 727 (ans+=tmp*rett[i]%mod*qp(m%mod,n-(i+1)))%=mod; 728 } 729 cout<<ans<<"\n"; 730 } 731 return 0; 732 } 733 ``` 734 735 $\mathcal O(\sum m\log n)$ solution by [ling_luo](/profile/ling_luo "Grandmaster ling_luo"): 736 737 **Implementation** 738 739 ``` 740 #include <bits/stdc++.h> 741 #define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i) 742 #define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i) 743 #define mp make_pair 744 #define fi first 745 #define se second 746 typedef long long ll; 747 using namespace std; 748 const ll mod1=998244353; 749 int t; 750 ll n; 751 int m; 752 ll qkpw(ll a,ll b) 753 { 754 ll ret=1; 755 while(b) 756 { 757 if(b&1) ret=ret*a%mod1; 758 a=a*a%mod1; 759 b>>=1; 760 } 761 return ret; 762 } 763 ll val_full[114]; 764 ll val_link[114]; 765 pair<ll,ll> realget(ll P,unsigned long long c) 766 { 767 if((c&(c+1))==0) 768 return mp(val_link[bit_width(c)-1],val_full[bit_width(c)-1]); 769 if(c==2) 770 return mp((P*P+P)%mod1,(P*P+P+P)%mod1); 771 if(c&(bit_floor(c)>>1)) 772 { 773 pair<ll,ll> A=realget(P,bit_floor(c)-1),B=realget(P,c-bit_floor(c)); 774 return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1); 775 } 776 pair<ll,ll> A=realget(P,c-(bit_floor(c)>>1)),B=realget(P,(bit_floor(c)>>1)-1); 777 return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1); 778 } 779 ll get_value(ll P,ll c) 780 { 781 val_full[0]=P;val_link[0]=P; 782 rep1(i,64) 783 { 784 val_full[i]=(val_full[i-1]*2+(1+val_link[i-1])*(1+val_link[i-1])%mod1*P)%mod1; 785 val_link[i]=((val_link[i-1]*2+1)*P)%mod1; 786 } 787 return realget(P,c).second; 788 } 789 void Q() 790 { 791 cin>>n>>m; 792 ll cur=((n%mod1)*(n%mod1+1)/2%mod1)*qkpw(m,n+1)%mod1; 793 ll INV_M=qkpw(m,mod1-2); 794 rep(i,m) cur=(cur-qkpw(m,n)*get_value(i*INV_M%mod1,n)%mod1+mod1)%mod1; 795 cout<<cur<<endl; 796 } 797 int main() 798 { 799 cin>>t;while(t--)Q(); 800 } 801 ``` 802 803 **Rate the problem** 804 805 * Amazing problem: 806 * Good problem: 807 * Average problem: 808 * Bad problem: 809 * Didn't solve: 810 811 [1868D - Flower-like Pseudotree](/contest/1868/problem/D "Codeforces Round 896 (Div. 1)") 812 813 Author: [sszcdjr](/profile/sszcdjr "Master sszcdjr") 814 815 **Hint 1** 816 817 In fact, vertices with degree $1$ are useless, let's first ignore them. It's easy to see that when $\sum_{i=1}^nd_i=2n$, we can simply hang them under the vertices which haven't reached their degree limit. 818 819 **Hint 2** 820 821 In most cases, we can simply put two vertices on the cycle. 822 823 **Hint 3** 824 825 Sort $d_i$ from the largest to the smallest. Can we construct a flower-like psuedotree when $d_1=2$? Can we construct a flower-like psuedotree when $d_1\neq 2$ and $d_2=2$? 826 827 **Hint 4** 828 829 Can you find an easy way to construct the flower-like psuedotree when the number of $d_i \gt 1$ is even? 830 831 **Hint 5** 832 833 Try to extend the solution when the number of $d_i \gt 1$ is even to the odd case. Note some corner cases. 834 835 **Solution** 836 837 Tutorial is loading... 838 839 **Implementation** 840 841 ``` 842 #include <bits/stdc++.h> 843 #define int long long 844 #define double long double 845 using namespace std; 846 struct node{ 847 int d,pos; 848 }a[1000005]; 849 bool cmp(node x,node y){ 850 return x.d>y.d; 851 } 852 void pe(int x,int y){ 853 cout<<a[x].pos<<" "<<a[y].pos<<"\n"; 854 } 855 signed main(){ 856 ios::sync_with_stdio(false); 857 cin.tie(0),cout.tie(0); 858 int t; cin>>t; 859 while(t--){ 860 int n,tot=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].d,a[i].pos=i,tot+=a[i].d; 861 if(tot!=2*n){ 862 cout<<"No\n"; continue; 863 } 864 if(n==1){ 865 cout<<"No\n"; continue; 866 } 867 sort(a+1,a+n+1,cmp); 868 if(a[1].d==2){ 869 cout<<"Yes\n"; 870 for(int i=1;i<=n;i++) pe(i,i%n+1); 871 continue; 872 } 873 if(a[2].d==2){ 874 cout<<"No\n"; continue; 875 } 876 int cntb=0; 877 for(int i=3;i<=n;i++) cntb+=(a[i].d>1); 878 int num[n+1]; for(int i=1;i<=n;i++) num[i]=a[i].d; 879 if(!(cntb&1)){ 880 cout<<"Yes\n"; 881 pe(1,2),pe(1,2); 882 num[1]-=2,num[2]-=2; 883 for(int i=3;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--; 884 int it=1; 885 for(int i=cntb+3;i<=n;i++){ 886 while(!num[it]) it++; 887 num[it]--,pe(i,it); 888 } 889 continue; 890 } 891 if(a[1].d==3){ 892 if(a[3].d==2){ 893 cout<<"No\n"; continue; 894 } 895 if(cntb==1){ 896 cout<<"Yes\n"; 897 pe(1,2),pe(2,3),pe(3,1); 898 pe(1,4),pe(2,5),pe(3,6); 899 continue; 900 } 901 if(a[5].d==2&&cntb==3){ 902 cout<<"No\n"; continue; 903 } 904 if(cntb==3){ 905 cout<<"Yes\n"; 906 pe(1,2),pe(2,3),pe(3,4),pe(4,5),pe(5,1); 907 pe(1,6),pe(2,7),pe(3,8),pe(4,9),pe(5,10); 908 continue; 909 } 910 cout<<"Yes\n"; 911 pe(1,2),pe(1,2),pe(1,3),pe(2,4),pe(3,5),pe(3,6),pe(4,7); 912 num[1]-=3,num[2]-=3,num[3]-=3,num[4]-=2,num[5]--,num[6]--,num[7]--; 913 for(int i=8;i<=cntb+2;i++) pe(i-2,i),num[i]--,num[i-2]--; 914 int it=1; 915 for(int i=cntb+3;i<=n;i++){ 916 while(!num[it]) it++; 917 num[it]--,pe(i,it); 918 } 919 continue; 920 } 921 else{ 922 if(a[3].d==2&&cntb==1){ 923 cout<<"No\n"; continue; 924 } 925 if(cntb==1){ 926 cout<<"Yes\n"; 927 pe(1,2),pe(2,3),pe(3,1); 928 num[1]-=2,num[2]-=2,num[3]-=2; 929 int it=1; 930 for(int i=4;i<=n;i++){ 931 while(!num[it]) it++; 932 num[it]--,pe(i,it); 933 } 934 continue; 935 } 936 cout<<"Yes\n"; 937 pe(1,2),pe(1,2),pe(1,3),pe(1,4),pe(2,5); 938 num[1]-=4,num[2]-=3,num[3]-=1,num[4]-=1,num[5]-=1; 939 for(int i=6;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--; 940 int it=1; 941 for(int i=cntb+3;i<=n;i++){ 942 while(!num[it]) it++; 943 num[it]--,pe(i,it); 944 } 945 continue; 946 } 947 } 948 return 0; 949 } 950 ``` 951 952 **Rate the problem** 953 954 * Amazing problem: 955 * Good problem: 956 * Average problem: 957 * Bad problem: 958 * Didn't solve: 959 960 [1868E - Min-Sum-Max](/contest/1868/problem/E "Codeforces Round 896 (Div. 1)") 961 962 Author: [duck_pear](/profile/duck_pear "Master duck_pear") 963 Huge thanks to [Kubic](/profile/Kubic "International Grandmaster Kubic") for the development of this problem! 964 965 **Hint 1** 966 967 Consider this problem on the prefix sum array. 968 969 **Hint 2** 970 971 Try to make some observations about the prefix sum array. Consider dp. 972 973 **Hint 3** 974 975 Go for a slow solution first, for example, $\mathcal{O}(n^6)$ or $\mathcal{O}(n^4)$. 976 977 **Hint 4** 978 979 The last step is to optimize your dp to $\mathcal{O}(n^3)$. :) 980 981 **Fun Fact** 982 983 $\mathcal{O}(n^6)$ can pass $n\le 100$ easily so we have to raise the limit for $\sum n$ to $1~000$. 984 985 **Solution** 986 987 Tutorial is loading... 988 989 **Implementation (by Artyom123)** 990 991 ``` 992 #include <iostream> 993 #include <vector> 994 #include <string> 995 #include <algorithm> 996 #include <set> 997 #include <map> 998 #include <math.h> 999 #include <iomanip> 1000 #include <bitset> 1001 #include <random> 1002 #include <ctime> 1003 #include <string_view> 1004 #include <queue> 1005 #include <cassert> 1006 1007 using namespace std; 1008 1009 #define fi first 1010 #define se second 1011 #define all(x) (x).begin(), (x).end() 1012 #define pb emplace_back 1013 #define ll long long 1014 #define mp make_pair 1015 #define pii pair<int, int> 1016 #define ld long double 1017 1018 const int INF = 1e9 + 1; 1019 const ll INFLL = 1e18; 1020 1021 bool contains(ll x, ll l, ll r) { 1022 return (x >= l) && (x <= r); 1023 } 1024 1025 void solve() { 1026 int n; 1027 cin >> n; 1028 vector<ll> a(n + 1); 1029 for (int i = 1; i <= n; i++) cin >> a[i]; 1030 if (n == 1) { 1031 cout << 1 << "\n"; 1032 return; 1033 } 1034 vector<ll> pr(n + 1); 1035 for (int i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i + 1]; 1036 vector<vector<vector<int>>> dp_leftmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF))); 1037 vector<vector<vector<int>>> dp_leftmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF))); 1038 vector<vector<vector<int>>> dp_rightmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF))); 1039 vector<vector<vector<int>>> dp_rightmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF))); 1040 vector<pair<ll, int>> b(n + 1); 1041 for (int i = 0; i <= n; i++) b[i] = mp(pr[i], i); 1042 sort(all(b)); 1043 vector<vector<int>> next_left(n + 1, vector<int>(n + 1, -1)); 1044 vector<vector<int>> next_right(n + 1, vector<int>(n + 1, -1)); 1045 for (int i = 0; i <= n; i++) { 1046 int prev = -1; 1047 for (int j = 0; j <= n; j++) { 1048 next_left[i][j] = prev; 1049 if (pr[j] == pr[i]) prev = j; 1050 } 1051 prev = n + 1; 1052 for (int j = n; j >= 0; j--) { 1053 next_right[i][j] = prev; 1054 if (pr[j] == pr[i]) prev = j; 1055 } 1056 } 1057 for (int len = 0; len <= n; len++) { 1058 for (int i = 0; i <= n && i + len <= n; i++) { 1059 int j = i + len; 1060 for (int k = 0; k <= n; k++) { 1061 if (contains(pr[i], pr[i], pr[k]) && contains(pr[j], pr[i], pr[k])) dp_leftmin[i][j][k] = min(len, 1); 1062 if (contains(pr[i], pr[k], pr[i]) && contains(pr[j], pr[k], pr[i])) dp_leftmax[i][j][k] = min(len, 1); 1063 if (contains(pr[i], pr[j], pr[k]) && contains(pr[j], pr[j], pr[k])) dp_rightmin[i][j][k] = min(len, 1); 1064 if (contains(pr[i], pr[k], pr[j]) && contains(pr[j], pr[k], pr[j])) dp_rightmax[i][j][k] = min(len, 1); 1065 } 1066 if (len <= 1) continue; 1067 for (int x = i; x <= j; x++) { 1068 if (next_left[i][x] >= i) { 1069 int y = next_left[i][x]; 1070 if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][y][x] + dp_leftmax[x][j][i] + 1); 1071 if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][y][x] + dp_leftmin[x][j][i] + 1); 1072 } 1073 if (next_left[j][x] >= i) { 1074 int y = next_left[j][x]; 1075 if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[x][j][x] + dp_rightmin[i][y][x] + 1); 1076 if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[x][j][x] + dp_rightmax[i][y][x] + 1); 1077 } 1078 if (next_right[i][x] <= j) { 1079 int y = next_right[i][x]; 1080 if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][x][x] + dp_leftmin[y][j][x] + 1); 1081 if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][x][x] + dp_leftmax[y][j][x] + 1); 1082 } 1083 if (next_right[j][x] <= j) { 1084 int y = next_right[j][x]; 1085 if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[y][j][x] + dp_rightmax[i][x][j] + 1); 1086 if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[y][j][x] + dp_rightmin[i][x][j] + 1); 1087 } 1088 } 1089 int mx_left = -INF; 1090 int mx_right = -INF; 1091 for (int k = 0; k <= n; k++) { 1092 int p = k; 1093 while (p <= n && b[p].fi == b[k].fi) { 1094 mx_left = max(mx_left, dp_leftmin[i][j][b[p].se]); 1095 mx_right = max(mx_right, dp_rightmin[i][j][b[p].se]); 1096 p++; 1097 } 1098 for (int l = k; l < p; l++) { 1099 dp_leftmin[i][j][b[l].se] = mx_left; 1100 dp_rightmin[i][j][b[l].se] = mx_right; 1101 } 1102 k = p - 1; 1103 } 1104 mx_left = -INF; 1105 mx_right = -INF; 1106 for (int k = n; k >= 0; k--) { 1107 int p = k; 1108 while (p >= 0 && b[p].fi == b[k].fi) { 1109 mx_left = max(mx_left, dp_leftmax[i][j][b[p].se]); 1110 mx_right = max(mx_right, dp_rightmax[i][j][b[p].se]); 1111 p--; 1112 } 1113 for (int l = k; l > p; l--) { 1114 dp_leftmax[i][j][b[l].se] = mx_left; 1115 dp_rightmax[i][j][b[l].se] = mx_right; 1116 } 1117 k = p + 1; 1118 } 1119 } 1120 } 1121 int ans = -INF; 1122 ans = max(ans, dp_leftmin[0][n][n]); 1123 ans = max(ans, dp_leftmax[0][n][n]); 1124 for (int x = 0; x <= n; x++) { 1125 for (int y = x + 1; y <= n; y++) { 1126 ans = max(ans, dp_rightmin[0][x][y] + dp_leftmax[y][n][x] + 1); 1127 ans = max(ans, dp_rightmax[0][x][y] + dp_leftmin[y][n][x] + 1); 1128 } 1129 } 1130 cout << ans << "\n"; 1131 } 1132 1133 int main() { 1134 #ifdef LOCAL 1135 freopen("input", "r", stdin); 1136 freopen("output", "w", stdout); 1137 #else 1138 ios_base::sync_with_stdio(0); 1139 cin.tie(0); 1140 cout.tie(0); 1141 #endif 1142 int t; 1143 cin >> t; 1144 while (t--) { 1145 solve(); 1146 } 1147 return 0; 1148 } 1149 ``` 1150 1151 **Rate the problem** 1152 1153 * Amazing problem: 1154 * Good problem: 1155 * Average problem: 1156 * Bad problem: 1157 * Didn't solve: 1158 1159 [1868F - LIS?](/contest/1868/problem/F "Codeforces Round 896 (Div. 1)") 1160 1161 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan") 1162 1163 **Hint 1** 1164 1165 Greedy. 1166 1167 **Hint 2** 1168 1169 This problem is somehow related to geometry. 1170 1171 **Hint 3** 1172 1173 What structure will the intervals you choose each time form? 1174 1175 **Solution** 1176 1177 Tutorial is loading... 1178 1179 **Implementation** 1180 1181 ``` 1182 #include <bits/stdc++.h> 1183 #define all(s) s.begin(), s.end() 1184 using namespace std; 1185 using ll = long long; 1186 using ull = unsigned long long; 1187 using point = pair<ll, ll>; 1188 1189 const int _N = 5e5 + 5; 1190 1191 int n; 1192 ll a[_N], pre[_N], suf[_N], ans; 1193 struct interval{ 1194 int l, r; 1195 ll d, dneed; 1196 int type, pos; // type0 - l, type1 - r 1197 }; 1198 struct cmp{ 1199 bool operator () (const interval &a, const interval &b) { 1200 return a.dneed - a.d > b.dneed - b.d; 1201 } 1202 }; 1203 1204 ll ceildiv(ll a, ll b) { 1205 // return a/b; 1206 if (a * b > 0) return a / b; 1207 else return a / b - !!(a % b); 1208 } 1209 1210 namespace sg_left{ // [l, r] -> hull of point l-1 to r-1 1211 vector<int> hull[_N << 2]; 1212 point pt[_N]; 1213 void get_hull(int p, int l, int r) { 1214 int head = 0, tail = -1; 1215 for (int i = l; i <= r; i++) { 1216 while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) <= (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) { 1217 tail--; 1218 hull[p].pop_back(); 1219 } 1220 tail++; 1221 hull[p].emplace_back(i); 1222 } 1223 } 1224 void build(int p, int l, int r) { 1225 get_hull(p, l - 1, r - 1); 1226 if (l == r) return; 1227 int mid = (l + r) >> 1; 1228 build(p * 2, l, mid); 1229 build(p * 2 + 1, mid + 1, r); 1230 } 1231 pair<int, int> query(int p, int l, int r, int L, int R, point o) { 1232 if (l >= L && r <= R) { // do ternary search 1233 int tl = 1, tr = hull[p].size(); 1234 while (tl < tr) { 1235 int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1; 1236 auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]]; 1237 if ((o.second - p1.second) * (o.first - p2.first) >= (o.second - p2.second) * (o.first - p1.first)) { 1238 tl = m1 + 1; 1239 } else tr = m2 - 1; 1240 } 1241 return {ceildiv((o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] + 1}; 1242 } 1243 int mid = (l + r) >> 1; 1244 pair<int, int> res = {-1, -1}; 1245 if (L <= mid) { 1246 res = query(p * 2, l, mid, L, R, o); 1247 } 1248 if (R > mid) { 1249 auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o); 1250 if (res == make_pair(-1, -1)) return res2; 1251 else { 1252 if (res2.first <= res.first) { 1253 return res2; 1254 } else return res; 1255 } 1256 } 1257 return res; 1258 } 1259 void test() { 1260 auto res = query(1, 1, n, 1, n, pt[n]); 1261 cout << res.first << ' ' << res.second << '\n'; 1262 } 1263 }; 1264 namespace sg_right{ // [l, r] -> hull of point l+1 to r+1 1265 vector<int> hull[_N << 2]; 1266 point pt[_N]; 1267 void get_hull(int p, int l, int r) { 1268 int head = 0, tail = -1; 1269 for (int i = l; i <= r; i++) { 1270 while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) < (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) { 1271 tail--; 1272 hull[p].pop_back(); 1273 } 1274 tail++; 1275 hull[p].emplace_back(i); 1276 } 1277 } 1278 void build(int p, int l, int r) { 1279 get_hull(p, l + 1, r + 1); 1280 if (l == r) return; 1281 int mid = (l + r) >> 1; 1282 build(p * 2, l, mid); 1283 build(p * 2 + 1, mid + 1, r); 1284 } 1285 pair<int, int> query(int p, int l, int r, int L, int R, point o) { 1286 if (l >= L && r <= R) { // do ternary search 1287 int tl = 1, tr = hull[p].size(); 1288 while (tl < tr) { 1289 int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1; 1290 auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]]; 1291 if ((o.second - p1.second) * (o.first - p2.first) <= (o.second - p2.second) * (o.first - p1.first)) { 1292 tl = m1 + 1; 1293 } else tr = m2 - 1; 1294 } 1295 return {ceildiv(-(o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] - 1}; 1296 } 1297 int mid = (l + r) >> 1; 1298 pair<int, int> res = {-1, -1}; 1299 if (L <= mid) { 1300 res = query(p * 2, l, mid, L, R, o); 1301 } 1302 if (R > mid) { 1303 auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o); 1304 if (res == make_pair(-1, -1)) return res2; 1305 else { 1306 if (res.first <= res2.first) { 1307 return res; 1308 } else return res2; 1309 } 1310 } 1311 return res; 1312 } 1313 void test() { 1314 auto res = query(1, 1, n, 1, n, pt[1]); 1315 cout << res.first << ' ' << res.second << '\n'; 1316 } 1317 }; 1318 1319 int main() { 1320 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 1321 cin >> n; 1322 for (int i = 1; i <= n; i++) cin >> a[i]; 1323 if (n == 1) { 1324 cout << max(a[1] + 1, 0ll) << '\n'; 1325 return 0; 1326 } 1327 sg_left::pt[0] = {0, 0}; sg_right::pt[n + 1] = {n + 1, 0}; 1328 for (int i = 1; i <= n; i++) { 1329 pre[i] = pre[i - 1] + a[i]; 1330 sg_left::pt[i] = {i, pre[i]}; 1331 } 1332 for (int i = n; i >= 1; i--) { 1333 suf[i] = suf[i + 1] + a[i]; 1334 sg_right::pt[i] = {i, suf[i]}; 1335 } 1336 sg_left::build(1, 1, n); 1337 sg_right::build(1, 1, n); 1338 ll ans = 0; 1339 priority_queue<interval, vector<interval>, cmp> q; 1340 pair<int, int> resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]); 1341 pair<int, int> resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]); 1342 if (resL.second == 1) q.push({1, n, 0, resR.first + 1, 1, resR.second}); 1343 else if (resR.second == n) q.push({1, n, 0, resL.first + 1, 0, resL.second}); 1344 else if (resL.first <= resR.first) q.push({1, n, 0, resL.first + 1, 0, resL.second}); 1345 else q.push({1, n, 0, resR.first + 1, 1, resR.second}); 1346 while (!q.empty()) { 1347 auto x = q.top(); q.pop(); 1348 if (x.d < x.dneed) { 1349 ans += x.dneed - x.d; 1350 x.d = x.dneed; 1351 } 1352 //split 1353 if (x.type == 1) x.pos++; 1354 int l = x.l, r = x.r; 1355 resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]); 1356 resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]); 1357 if (l == x.pos - 1) { 1358 ans += max(0ll, a[l] - x.d + 1); 1359 } else { 1360 if (resL.second == l) q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second}); 1361 else if (resR.second == r) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second}); 1362 else if (resL.first <= resR.first) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second}); 1363 else q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second}); 1364 } 1365 resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]); 1366 resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]); 1367 if (x.pos == r) { 1368 ans += max(0ll, a[r] - x.d + 1); 1369 } else { 1370 if (resL.second == l) q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second}); 1371 else if (resR.second == r)q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second}); 1372 else if (resL.first < resR.first) q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second}); 1373 else q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second}); 1374 } 1375 } 1376 cout << ans << '\n'; 1377 } 1378 ``` 1379 1380 **Bonus** 1381 1382 Can you solve this problem in $\mathcal{O}(n\log n+n\log V)$ time complexity and $\mathcal{O}(n)$ space complexity? 1383 1384 **Hint for Bonus** 1385 1386 The solution has nothing to do with data structures. 1387 1388 Bonus solution by [duck_pear](/profile/duck_pear "Master duck_pear"): 1389 1390 **Implementation** 1391 1392 ``` 1393 /* 1394 hmz is cute! 1395 -------------------------------------------- 1396 You've got to have faith 1397 Don't let them cut you down cut you down once more 1398 */ 1399 //#pragma GCC optimize("Ofast,no-stack-protector") 1400 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 1401 #include<bits/stdc++.h> 1402 using namespace std; 1403 #define TY long long 1404 #define IL inline 1405 #define umap unordered_map 1406 #define ull unsigned long long 1407 #define pq priority_queue 1408 #define mp make_pair 1409 #define pb push_back 1410 #define mod (TY)(1e9+7) 1411 #define MAXN 500005 1412 #define MAXM 200005 1413 #define MAXK 27 1414 #define INF (TY)(1e9) 1415 #define block 300 1416 #define For(i,a,b) for(TY i=(a);i<=(b);++i) 1417 #define FOR(i,a,b) for(TY i=(a);i<(b);++i) 1418 #define Rof(i,a,b) for(TY i=(a);i>=(b);--i) 1419 #define ROF(i,a,b) for(TY i=(a);i>(b);--i) 1420 IL TY qr(){ 1421 TY x=0,f=1;char op=getchar(); 1422 for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1; 1423 for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48); 1424 return x*f; 1425 }IL bool ischar(char op){ 1426 if(op>='a'&&op<='z')return true; 1427 if(op>='A'&&op<='Z')return true; 1428 return false; 1429 }IL char getc(){ 1430 char op=getchar(); 1431 while(!ischar(op))op=getchar(); 1432 return op; 1433 }IL string qs(){ 1434 string op="";char u=getchar(); 1435 while(!ischar(u))u=getchar(); 1436 while(ischar(u))op+=u,u=getchar(); 1437 return op; 1438 }IL void qw(long long x){ 1439 if(!x){putchar('0');return;} 1440 if(x<0)putchar('-'),x=-x; 1441 if(x>=10)qw(x/10);putchar(x%10+'0'); 1442 }IL void qw(long long x,char op){qw(x),putchar(op);} 1443 IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);} 1444 IL TY Ceil(TY a,TY b){return a/b+(a%b!=0);} 1445 IL TY Mod(TY a){return (a>=mod?a-mod:a);} 1446 IL TY Abs(TY a,TY b){return a>b?a-b:b-a;} 1447 IL TY Pow(TY a,TY b){ 1448 TY ans=1,base=a; 1449 while(b){ 1450 if(b&1)ans=ans*base%mod; 1451 base=base*base%mod;b>>=1; 1452 }return ans; 1453 }TY n,a[MAXN],b[MAXN],sum[MAXN],lenx[MAXN],leny[MAXN],ans; 1454 vector<signed> e1[MAXN],e2[MAXN],HH; 1455 TY Sum[MAXN],SSum[MAXN]; 1456 bool vis[MAXN]; 1457 signed L[MAXN],R[MAXN],LL[MAXN],RR[MAXN],ok[MAXN],nxtx[MAXN],nxty[MAXN]; 1458 struct node{TY l,r,tag,op;};queue<node> q; 1459 IL void init(TY l,TY r,TY tag){ 1460 For(i,l,r)e1[i].clear(),e2[i].clear(); 1461 vector<pair<TY,TY> > pre,nxt; 1462 For(i,l,r){ 1463 while(!pre.empty()){ 1464 TY ch=(pre.back().second*-1+tag)*(i-pre.back().first)+sum[i]-sum[pre.back().first]; 1465 if(ch<0){ 1466 nxtx[pre.back().first]=i; 1467 pre.pop_back();continue; 1468 }else{ 1469 lenx[i]=pre.back().second+Ceil(ch+1,i-pre.back().first); 1470 pre.push_back({i,pre.back().second+Ceil(ch+1,i-pre.back().first)}); 1471 break; 1472 } 1473 }if(pre.empty()){ 1474 lenx[i]=Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1); 1475 pre.push_back({i,Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1)}); 1476 } 1477 }while(!pre.empty())nxtx[pre.back().first]=r+1,pre.pop_back(); 1478 Rof(i,r,l){ 1479 while(!nxt.empty()){ 1480 TY ch=(nxt.back().second*-1+tag)*(nxt.back().first-i)-sum[i-1]+sum[nxt.back().first-1]; 1481 if(ch<0){ 1482 nxty[nxt.back().first]=i; 1483 nxt.pop_back();continue; 1484 }else{ 1485 leny[i]=nxt.back().second+Ceil(ch+1,nxt.back().first-i); 1486 nxt.push_back({i,nxt.back().second+Ceil(ch+1,nxt.back().first-i)}); 1487 break; 1488 } 1489 }if(nxt.empty()){ 1490 leny[i]=Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1); 1491 nxt.push_back({i,Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1)}); 1492 } 1493 }while(!nxt.empty())nxty[nxt.back().first]=l-1,nxt.pop_back(); 1494 For(i,l,r)if(nxtx[i]!=r+1)e1[nxtx[i]].pb(i); 1495 Rof(i,r,l)if(nxty[i]!=l-1)e2[nxty[i]].pb(i); 1496 }int main(){ 1497 //freopen("data.in","r",stdin); 1498 /* init */ 1499 n=qr();For(i,1,n)a[i]=qr(),sum[i]=sum[i-1]+a[i]; 1500 q.push({1,n,0,0}); 1501 while(!q.empty()){ 1502 TY l=q.front().l,r=q.front().r,tag=q.front().tag,op=q.front().op; 1503 if(l>r||l<=0||r>n)continue; 1504 q.pop(); 1505 if(op==0){ 1506 vector<pair<TY,TY> > tmp; 1507 TY c=0;TY lst=-1; 1508 For(i,l,r)b[i]=a[i]+tag; 1509 For(i,l,r){ 1510 if((b[i]>=0)!=lst){ 1511 lst=(b[i]>=0); 1512 ++c;L[c]=R[c]=i; 1513 Sum[c]=b[i]; 1514 }else R[c]=i,Sum[c]+=b[i]; 1515 }For(i,1,c)LL[i]=i,RR[i]=i,SSum[i]=Sum[i],ok[i]=0,vis[i]=1; 1516 Sum[c+1]=0;RR[c+1]=INF; 1517 For(i,1,c)if(Sum[i]<0){ 1518 ok[i]=(Sum[i-1]+Sum[i]>=0)+(Sum[i+1]+Sum[i]>=0); 1519 if(ok[i]==2)HH.pb(i),ok[i]=INF; 1520 }else{ 1521 ok[i]=(Sum[i-1]+Sum[i]<0)+(Sum[i+1]+Sum[i]<0); 1522 if(ok[i]==2)HH.pb(i),ok[i]=INF; 1523 }while(!HH.empty()){ 1524 TY now=HH.back(),nowL=LL[now],nowR=RR[now]; 1525 TY k=SSum[nowL]+SSum[nowL-1]+SSum[nowR+1],pre=LL[LL[nowL-1]-1],nxt=RR[nowR+1]+1; 1526 HH.pop_back(); 1527 if(SSum[nowL]>=0){ 1528 if(pre>=1&&nxt<=c){ 1529 ok[LL[nowL-1]]=(k+SSum[pre]>=0)+(k+SSum[nxt]>=0); 1530 if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF; 1531 }else ok[LL[nowL-1]]=INF; 1532 if(pre>=1){ 1533 ok[pre]+=-(SSum[nowL-1]+SSum[pre]<0)+(SSum[pre]+k<0); 1534 if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]>=0)HH.pb(pre),ok[pre]=INF; 1535 }if(nxt<=c){ 1536 ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]<0)+(SSum[nxt]+k<0); 1537 if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]>=0)HH.pb(nxt),ok[nxt]=INF; 1538 } 1539 }else{ 1540 if(pre>=1&&nxt<=c){ 1541 ok[LL[nowL-1]]=(k+SSum[pre]<0)+(k+SSum[nxt]<0); 1542 if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF; 1543 }else ok[LL[nowL-1]]=INF; 1544 if(pre>=1){ 1545 ok[pre]+=-(SSum[nowL-1]+SSum[pre]>=0)+(SSum[pre]+k>=0); 1546 if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]<0)HH.pb(pre),ok[pre]=INF; 1547 }if(nxt<=c){ 1548 ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]>=0)+(SSum[nxt]+k>=0); 1549 if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]<0)HH.pb(nxt),ok[nxt]=INF; 1550 } 1551 }SSum[LL[nowL-1]]=SSum[RR[nowR+1]]=k; 1552 RR[LL[nowL-1]]=RR[nowR+1]; 1553 LL[RR[nowR+1]]=LL[nowL-1]; 1554 }Rof(i,c,1)if(Sum[i]>=0&&vis[i]){ 1555 Rof(j,i,LL[i])vis[j]=0; 1556 tmp.pb({L[LL[i]],R[RR[i]]}); 1557 }Rof(i,tmp.size()-1,0)q.push({tmp[i].first,tmp[i].second,tag,1}); 1558 }else{ 1559 if(l==r){ 1560 ans+=a[l]+tag+1; 1561 continue; 1562 }queue<TY> fir,sec; 1563 init(l,r,tag); 1564 For(i,l,r)if(nxtx[i]==r+1)fir.push(i); 1565 Rof(i,r,l)if(nxty[i]==l-1)sec.push(i); 1566 TY lstl=l,lstr=r,lstcnt=0; 1567 while(lstl<lstr){ 1568 while(!fir.empty()&&(lstl>fir.front()||fir.front()>lstr))fir.pop(); 1569 while(!sec.empty()&&(lstl>sec.front()||sec.front()>lstr))sec.pop(); 1570 TY id1=(fir.empty()?INF:fir.front()),id2=(sec.empty()?INF:sec.front()); 1571 TY cnt1=(id1==INF?INF:lenx[id1]-lstcnt); 1572 TY cnt2=(id2==INF?INF:leny[id2]-lstcnt); 1573 if(cnt1<=cnt2){ 1574 fir.pop(); 1575 lstcnt=lenx[id1]; 1576 For(j,lstl,id1){FOR(i,0,e2[j].size())sec.push(e2[j][i]);e2[j].clear();} 1577 q.push({lstl,id1,-lstcnt+tag,0}); 1578 lstl=id1+1; 1579 }else{ 1580 sec.pop(); 1581 lstcnt=leny[id2]; 1582 Rof(j,lstr,id2){FOR(i,0,e1[j].size())fir.push(e1[j][i]);e1[j].clear();} 1583 q.push({id2,lstr,-lstcnt+tag,0}); 1584 lstr=id2-1; 1585 } 1586 }if(lstl==lstr)q.push({lstl,lstl,-lstcnt+tag,1}); 1587 ans+=lstcnt; 1588 } 1589 }qw(ans); 1590 return 0; 1591 } 1592 ``` 1593 1594 **Rate the problem** 1595 1596 * Amazing problem: 1597 * Good problem: 1598 * Average problem: 1599 * Bad problem: 1600 * Didn't solve: