1527.md (27182B)
1 Source: https://codeforces.com/blog/entry/90939 2 3 [1527A - And Then There Were K](/contest/1527/problem/A "Codeforces Round 721 (Div. 2)") 4 5 Author: [loud_mouth](/profile/loud_mouth "Expert loud_mouth") 6 Idea: [Bignubie](/profile/Bignubie "Candidate Master Bignubie") 7 8 **Editorial** 9 10 Tutorial is loading... 11 12 **Solution (Loud_mouth)** 13 14 ``` 15 #include<bits/stdc++.h> 16 using namespace std; 17 #define ll long long 18 19 int main() 20 { 21 int t; 22 cin>>t; 23 while(t--) 24 { 25 int n; 26 cin>>n; 27 int last=0; 28 for(int i=0; i<30; ++i) 29 { 30 if(((n>>i)&1) == 1) 31 { 32 last=i; 33 } 34 } 35 cout<<(1<<last)-1<<"\n"; 36 } 37 return 0; 38 } 39 ``` 40 41 **Solution (the_nightmare)** 42 43 ``` 44 #include<bits/stdc++.h> 45 #include <ext/pb_ds/assoc_container.hpp> 46 #include <ext/pb_ds/tree_policy.hpp> 47 #define ll long long 48 #define pb push_back 49 #define ppb pop_back 50 #define endl '\n' 51 #define mii map<ll,ll> 52 #define msi map<string,ll> 53 #define mis map<ll, string> 54 #define rep(i,a,b) for(ll i=a;i<b;i++) 55 #define repr(i,a,b) for(ll i=b-1;i>=a;i--) 56 #define trav(a, x) for(auto& a : x) 57 #define pii pair<ll,ll> 58 #define vi vector<ll> 59 #define vii vector<pair<ll, ll>> 60 #define vs vector<string> 61 #define all(a) (a).begin(),(a).end() 62 #define F first 63 #define S second 64 #define sz(x) (ll)x.size() 65 #define hell 1000000007 66 #define lbnd lower_bound 67 #define ubnd upper_bound 68 #define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl; 69 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl; 70 #define what_is(x) cerr << #x << " is " << x << endl; 71 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 72 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 73 using namespace __gnu_pbds; 74 using namespace std; 75 #define PI 3.141592653589793 76 #define N 200005 77 void solve() 78 { 79 ll n; 80 cin >> n; 81 ll cnt=0; 82 while(n!=0){ 83 cnt++; 84 n=n/2; 85 } 86 cout << (1<<(cnt-1))-1 << endl; 87 } 88 int main() 89 { 90 #ifndef ONLINE_JUDGE 91 freopen ("input.txt","r",stdin); 92 #endif 93 ll int TEST=1; 94 cin >> TEST; 95 //init(); 96 while(TEST--) 97 { 98 solve(); 99 } 100 } 101 ``` 102 103 [1527B1 - Palindrome Game (easy version)](/contest/1527/problem/B1 "Codeforces Round 721 (Div. 2)") 104 105 Author: [DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR") 106 Idea: [shikhar7s](/profile/shikhar7s "Master shikhar7s") 107 108 **Editorial** 109 110 Tutorial is loading... 111 112 **Solution (DenOMINATOR)** 113 114 ``` 115 #include<bits/stdc++.h> 116 using namespace std; 117 118 void solve(){ 119 int n; 120 cin >> n; 121 string s; 122 cin >> s; 123 bool is_palindrome=1; 124 int cnt_0 = 0; 125 for(int i=0;i<n;i++){ 126 cnt_0 += s[i]=='0'; 127 } 128 if(cnt_0 == 1){ 129 cout << "BOB\n"; 130 return; 131 } 132 if(cnt_0%2){ 133 cout << "ALICE\n"; 134 return; 135 } 136 cout << "BOB\n"; 137 return; 138 } 139 140 signed main() 141 { 142 int t; 143 cin >> t; 144 while(t--){ 145 solve(); 146 } 147 return 0; 148 } 149 ``` 150 151 **Solution (shikhar7s)** 152 153 ``` 154 #include<bits/stdc++.h> 155 using namespace std; 156 #define int long long int 157 #define mp(a,b) make_pair(a,b) 158 #define vi vector<int> 159 #define mii map<int,int> 160 #define mpi map<pair<int,int>,int> 161 #define vp vector<pair<int,int> > 162 #define pb(a) push_back(a) 163 #define fr(i,n) for(i=0;i<n;i++) 164 #define rep(i,a,n) for(i=a;i<n;i++) 165 #define F first 166 #define S second 167 #define endl "\n" 168 #define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 169 #define mod 1000000007 170 #define dom 998244353 171 #define sl(a) (int)a.length() 172 #define sz(a) (int)a.size() 173 #define all(a) a.begin(),a.end() 174 #define pii pair<int,int> 175 #define mini 2000000000000000000 176 #define time_taken 1.0 * clock() / CLOCKS_PER_SEC 177 //const long double pi = acos(-1); 178 //mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); 179 //primes for hashing 937, 1013 180 template<typename T, typename U> static inline void amin(T &x, U y) 181 { 182 if (y < x) 183 x = y; 184 } 185 template<typename T, typename U> static inline void amax(T &x, U y) 186 { 187 if (x < y) 188 x = y; 189 } 190 void shikhar7s(int cas) 191 { 192 int n,i; 193 cin>>n; 194 string s; 195 cin>>s; 196 int f=1,z=0; 197 fr(i,n) 198 { 199 if(s[i]=='0') 200 z++; 201 } 202 int x=0; 203 fr(i,n/2) 204 { 205 if(s[i]!=s[n-1-i]) 206 { 207 f=0; 208 x++; 209 } 210 } 211 if(f) 212 { 213 if(z==1||z%2==0) 214 cout<<"BOB"<<endl; 215 else 216 cout<<"ALICE"<<endl; 217 } 218 else 219 { 220 if(x==1&&z==2) 221 cout<<"DRAW"<<endl; 222 else 223 cout<<"ALICE"<<endl; 224 } 225 } 226 signed main() 227 { 228 fast; 229 //freopen("input.txt", "rt", stdin); 230 //freopen("output.txt", "wt", stdout); 231 int t=1; 232 cin>>t; 233 int cas=1; 234 while(cas<=t) 235 { 236 //cout<<"Case #"<<cas<<": "; 237 shikhar7s(cas); 238 cas++; 239 } 240 return 0; 241 } 242 ``` 243 244 [1527B2 - Palindrome Game (hard version)](/contest/1527/problem/B2 "Codeforces Round 721 (Div. 2)") 245 246 Author: [DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR") 247 Idea:[DenOMINATOR](/profile/DenOMINATOR "Master DenOMINATOR") 248 249 **Editorial** 250 251 Tutorial is loading... 252 253 **Solution(Greedy) (DenOMINATOR)** 254 255 ``` 256 #include<bits/stdc++.h> 257 using namespace std; 258 259 void solve(){ 260 int n; 261 cin >> n; 262 string s; 263 cin >> s; 264 bool is_palindrome=1; 265 int cnt_0 = 0, cnt_1 = 0; 266 for(int i=0;i<n;i++){ 267 cnt_0 += s[i]=='0'; 268 } 269 for(int i=0;i<n/2;i++){ 270 if(s[i]!=s[n-1-i]) is_palindrome = 0; 271 if( (s[i]=='1' || s[n-1-i]=='1') && s[i]!=s[n-1-i]){ 272 cnt_1++; 273 } 274 } 275 if(is_palindrome){ 276 if(cnt_0 == 1){ 277 cout << "BOB\n"; 278 return; 279 } 280 if(cnt_0%2){ 281 cout << "ALICE\n"; 282 return; 283 } 284 cout << "BOB\n"; 285 return; 286 } 287 if(cnt_0==2 && cnt_1==1){ 288 cout << "DRAW\n"; 289 return; 290 } 291 cout << "ALICE\n"; 292 return; 293 } 294 295 signed main() 296 { 297 int t; 298 cin >> t; 299 while(t--){ 300 solve(); 301 } 302 return 0; 303 } 304 ``` 305 306 **Solution(DP) (DenOMINATOR)** 307 308 ``` 309 #include <bits/stdc++.h> 310 using namespace std; 311 312 typedef long long ll; 313 double pi = acos(-1); 314 #define _time_ 1.0 * clock() / CLOCKS_PER_SEC 315 #define fi first 316 #define se second 317 #define mp make_pair 318 #define pb push_back 319 #define all(a) a.begin(),a.end() 320 mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); 321 322 int dp[505][505][2][2]; 323 324 void precompute(){ 325 for(int i=0;i<=500;i++){ 326 for(int j=0;j<=500;j++){ 327 for(int k=0;k<2;k++){ 328 for(int l=1;l>=0;l--){ 329 dp[i][j][k][l] = 1e9; 330 } 331 } 332 } 333 } 334 dp[0][0][0][0]=0; 335 dp[0][0][0][1]=0; 336 for(int i=0;i<=500;i++){ 337 for(int j=0;j<=500;j++){ 338 for(int k=0;k<2;k++){ 339 for(int l=1;l>=0;l--){ 340 if(l==0 && j>0) dp[i][j][k][l] = min(dp[i][j][k][l],-dp[i][j][k][1]); 341 if(i>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i-1][j+1][k][0]); 342 if(j>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j-1][k][0]); 343 if(k==1) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j][0][0]); 344 } 345 } 346 } 347 } 348 } 349 350 void solve(){ 351 int n; 352 cin >> n; 353 string s; 354 cin >> s; 355 int cnt00=0,cnt01=0,mid=0; 356 for(int i=0;i<n/2;i++){ 357 if(s[i]=='0' && s[i]==s[n-i-1]) cnt00++; 358 if(s[i]!=s[n-i-1]) cnt01++; 359 } 360 if(n%2 && s[n/2]=='0') mid=1; 361 if(dp[cnt00][cnt01][mid][0]<0){ 362 cout << "ALICE"; 363 }else if(dp[cnt00][cnt01][mid][0]>0){ 364 cout << "BOB"; 365 }else{ 366 cout << "DRAW"; 367 } 368 } 369 370 int main(){ 371 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 372 //freopen("input.txt", "r", stdin); 373 //freopen("output.txt", "w", stdout); 374 #ifdef SIEVE 375 sieve(); 376 #endif 377 #ifdef NCR 378 init(); 379 #endif 380 precompute(); 381 int t; 382 cin >> t; 383 while(t--){ 384 solve(); 385 cout << "\n"; 386 } 387 return 0; 388 } 389 ``` 390 391 [1527C - Sequence Pair Weight](/contest/1527/problem/C "Codeforces Round 721 (Div. 2)") 392 393 Author: [sharabhagrawal25](/profile/sharabhagrawal25 "Master sharabhagrawal25") 394 Idea: [rivalq](/profile/rivalq "Master rivalq") 395 396 **Editorial** 397 398 Tutorial is loading... 399 400 **Solution (sharabhagrawal25)** 401 402 ``` 403 #include <bits/stdc++.h> 404 using namespace std; 405 406 int main(){ 407 int t; 408 cin >> t; 409 while(t--){ 410 int n; 411 cin >> n; 412 413 int a[n]; 414 for (int i = 0 ; i < n; i++){ 415 cin >> a[i]; 416 } 417 418 vector <long long> dp(n, 0); 419 420 map <long long,long long> value; 421 422 long long final_ans = 0; 423 424 for (long long i = 0 ; i < n ; i++){ 425 if (i > 0) dp[i] = dp[i - 1]; 426 427 if (value.count(a[i])){ 428 dp[i] += value[a[i]]; 429 } 430 431 value[a[i]] += (i + 1); 432 final_ans += dp[i]; 433 } 434 435 cout << final_ans << endl; 436 } 437 } 438 ``` 439 440 **Solution (mallick630)** 441 442 ``` 443 t = int(input()) 444 for j in range(t): 445 n = int(input()) 446 a = list(map(int,input().split())) 447 448 value = {} 449 fa, ca = 0, 0 450 451 for i in range(n): 452 if a[i] in value: 453 ca += value[a[i]] 454 else: 455 value[a[i]]=0 456 value[a[i]] += i+1 457 fa += ca 458 459 print(fa) 460 ``` 461 462 [1527D - MEX Tree](/contest/1527/problem/D "Codeforces Round 721 (Div. 2)") 463 464 Author: [mallick630](/profile/mallick630 "Candidate Master mallick630") 465 Idea: [CoderAnshu](/profile/CoderAnshu "International Master CoderAnshu") 466 467 **Editorial** 468 469 Tutorial is loading... 470 471 **Solution (shikhar7s)** 472 473 ``` 474 #include<bits/stdc++.h> 475 using namespace std; 476 #define int long long int 477 #define mp(a,b) make_pair(a,b) 478 #define vi vector<int> 479 #define mii map<int,int> 480 #define mpi map<pair<int,int>,int> 481 #define vp vector<pair<int,int> > 482 #define pb(a) push_back(a) 483 #define fr(i,n) for(i=0;i<n;i++) 484 #define rep(i,a,n) for(i=a;i<n;i++) 485 #define F first 486 #define S second 487 #define endl "\n" 488 #define Endl "\n" 489 #define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 490 #define mod 1000000007 491 #define dom 998244353 492 #define sl(a) (int)a.length() 493 #define sz(a) (int)a.size() 494 #define all(a) a.begin(),a.end() 495 #define pii pair<int,int> 496 #define mini 2000000000000000000 497 #define time_taken 1.0 * clock() / CLOCKS_PER_SEC 498 //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 499 //const long double pi = acos(-1); 500 //mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); 501 //primes for hashing 937, 1013 502 template<typename T, typename U> static inline void amin(T &x, U y) 503 { 504 if (y < x) 505 x = y; 506 } 507 template<typename T, typename U> static inline void amax(T &x, U y) 508 { 509 if (x < y) 510 x = y; 511 } 512 vector<int> adj[200005]; 513 int vis[200005],c[200005],t; 514 pii p[200005]; 515 void dfs(int x) 516 { 517 vis[x]=1; 518 c[x]=1; 519 int i; 520 p[x]=mp(t,t); 521 t++; 522 fr(i,sz(adj[x])) 523 { 524 if(!vis[adj[x][i]]) 525 { 526 dfs(adj[x][i]); 527 c[x]+=c[adj[x][i]]; 528 p[x].S=p[adj[x][i]].S; 529 } 530 } 531 } 532 void shikhar7s(int cas) 533 { 534 int n,i; 535 cin>>n; 536 t=0; 537 fr(i,n) 538 { 539 vis[i]=0; 540 adj[i].clear(); 541 } 542 int x,y; 543 fr(i,n-1) 544 { 545 cin>>x>>y; 546 adj[x].pb(y); 547 adj[y].pb(x); 548 } 549 dfs(0); 550 int ans=0; 551 fr(i,sz(adj[0])) 552 { 553 int x=c[adj[0][i]]; 554 x=(x*(x-1))/2; 555 ans+=x; 556 } 557 cout<<ans<<" "; 558 int s=0,ss=0,got=1; 559 y=-1; 560 fr(i,sz(adj[0])) 561 { 562 int x=c[adj[0][i]]; 563 if(p[adj[0][i]].F<=p[1].F&&p[adj[0][i]].S>=p[1].S) 564 { 565 y=adj[0][i]; 566 x-=c[1]; 567 } 568 if(adj[0][i]!=y) 569 got+=x; 570 s+=x; 571 x*=x; 572 ss+=x; 573 } 574 ans=(s*s-ss)/2; 575 ans+=s; 576 cout<<ans<<" "; 577 i=2; 578 int l=0,r=1,j,b=0; 579 while(i<n) 580 { 581 if((p[i].F<=p[l].F&&p[i].S>=p[l].S)||(p[i].F<=p[r].F&&p[i].S>=p[r].S)) 582 { 583 cout<<0<<" "; 584 i++; 585 continue; 586 } 587 if(!l) 588 { 589 int f=2; 590 ss=c[r]; 591 if(p[r].F<=p[i].F&&p[r].S>=p[i].S) 592 { 593 f=1; 594 ss-=c[i]; 595 } 596 if(!(p[y].F<=p[i].F&&p[y].S>=p[i].S)) 597 { 598 ans=1; 599 fr(j,sz(adj[0])) 600 { 601 int x=adj[0][j]; 602 if(x==y) 603 continue; 604 int su=c[x]; 605 if(p[x].F<=p[i].F&&p[x].S>=p[i].S) 606 { 607 f=0; 608 su-=c[i]; 609 } 610 ans+=su; 611 } 612 } 613 else 614 ans=got; 615 ans*=ss; 616 cout<<ans<<" "; 617 if(!f) 618 l=i; 619 else if(f==1) 620 r=i; 621 else 622 { 623 i++; 624 b=1; 625 break; 626 } 627 } 628 else 629 { 630 int f=2; 631 s=c[l]; 632 ss=c[r]; 633 if(p[l].F<=p[i].F&&p[l].S>=p[i].S) 634 { 635 f=0; 636 s-=c[i]; 637 } 638 if(p[r].F<=p[i].F&&p[r].S>=p[i].S) 639 { 640 f=1; 641 ss-=c[i]; 642 } 643 ans=s*ss; 644 cout<<ans<<" "; 645 if(!f) 646 l=i; 647 else if(f==1) 648 r=i; 649 else 650 { 651 i++; 652 b=1; 653 break; 654 } 655 } 656 i++; 657 } 658 if(!b) 659 cout<<1<<" "; 660 else 661 { 662 while(i<=n) 663 { 664 cout<<0<<" "; 665 i++; 666 } 667 } 668 cout<<endl; 669 } 670 signed main() 671 { 672 fast; 673 //freopen("output.txt", "rt", stdin); 674 //freopen("output.txt", "wt", stdout); 675 int t=1; 676 cin>>t; 677 int cas=1; 678 while(cas<=t) 679 { 680 //cout<<"Case #"<<cas<<": "; 681 shikhar7s(cas); 682 cas++; 683 } 684 return 0; 685 } 686 ``` 687 688 **Solution (the_nightmare)** 689 690 ``` 691 #include<bits/stdc++.h> 692 #include <ext/pb_ds/assoc_container.hpp> 693 #include <ext/pb_ds/tree_policy.hpp> 694 #define ll long long 695 #define pb push_back 696 #define ppb pop_back 697 #define endl '\n' 698 #define mii map<ll,ll> 699 #define msi map<string,ll> 700 #define mis map<ll, string> 701 #define rep(i,a,b) for(ll i=a;i<b;i++) 702 #define repr(i,a,b) for(ll i=b-1;i>=a;i--) 703 #define trav(a, x) for(auto& a : x) 704 #define pii pair<ll,ll> 705 #define vi vector<ll> 706 #define vii vector<pair<ll, ll>> 707 #define vs vector<string> 708 #define all(a) (a).begin(),(a).end() 709 #define F first 710 #define S second 711 #define sz(x) (ll)x.size() 712 #define hell 1000000007 713 #define lbnd lower_bound 714 #define ubnd upper_bound 715 #define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl; 716 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl; 717 #define what_is(x) cerr << #x << " is " << x << endl; 718 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 719 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 720 using namespace __gnu_pbds; 721 using namespace std; 722 #define PI 3.141592653589793 723 #define N 200005 724 ll add(ll x,ll y){return (x+y)%hell;} 725 ll mul(ll x,ll y){return (x*y)%hell;} 726 vector <ll> adj[N]; 727 ll subtree[N]; 728 ll min1[N]; 729 ll ans[N]; 730 ll vis[N]; 731 ll le; 732 int v;int u; 733 ll n; 734 int prevv;int prevu; 735 void init(){ 736 rep(i,0,n){ 737 adj[i].clear(); 738 subtree[i]=0; 739 min1[i]=n; 740 ans[i]=0; 741 vis[i]=0; 742 } 743 le=n*(n-1)/2; 744 v=0;u=0; 745 prevv=-1; 746 prevu=-1; 747 } 748 void dfs(int v,int prev=-1){ 749 subtree[v]=1; 750 min1[v]=v; 751 for (auto it: adj[v]){ 752 if (it==prev) continue; 753 dfs(it,v); 754 subtree[v]+=subtree[it]; 755 min1[v]=min(min1[v],min1[it]); 756 } 757 } 758 void find(int val){ 759 //cout << v << " " << u << " " << prevv << " " << prevu << " " << val << endl; 760 if (v==val or u==val){ 761 ll a,b; 762 if (subtree[prevv]>subtree[v] or prevv==-1) a=subtree[v]; 763 else a=n-subtree[prevv]; 764 if (subtree[prevu]>subtree[u] or prevu==-1) b=subtree[u]; 765 else b=n-subtree[prevu]; 766 ans[val]=le-a*b; 767 //cout << a << " " << b << endl; 768 le=a*b; 769 return; 770 } 771 for (auto it: adj[v]){ 772 if (it==prevv) continue; 773 if (min1[it]==val){ 774 if (v==u) prevu=it; 775 prevv=v; 776 v=it; 777 vis[it]=1; 778 779 find(val); 780 return; 781 } 782 } 783 for (auto it: adj[u]){ 784 if (it==prevu) continue; 785 if (min1[it]==val){ 786 prevu=u; 787 u=it; 788 vis[it]=1; 789 find(val); 790 return; 791 } 792 } 793 ans[val]=le; 794 le=0; 795 } 796 void solve() 797 { 798 cin >> n; 799 init(); 800 rep(i,0,n-1){ 801 int x,y; 802 cin >> x >> y; 803 adj[x].pb(y); 804 adj[y].pb(x); 805 } 806 dfs(0); 807 //cout << le << endl; 808 for (auto it: adj[0]) {ans[0]+=(subtree[it]*(subtree[it]-1))/2;} 809 //cout << endl; 810 //cout << ans[0] << endl; 811 le-=ans[0]; 812 rep(i,1,n){ 813 if (vis[i]==1 or le==0) ans[i]=0; 814 else find(i); 815 } 816 ans[n]=le; 817 rep(i,0,n+1) cout << ans[i] << " "; 818 cout << endl; 819 return; 820 } 821 int main() 822 { 823 #ifndef ONLINE_JUDGE 824 freopen ("input.txt","r",stdin); 825 #endif 826 ll int TEST=1; 827 cin >> TEST; 828 while(TEST--) 829 { 830 solve(); 831 } 832 } 833 ``` 834 835 [1527E - Partition Game](/contest/1527/problem/E "Codeforces Round 721 (Div. 2)") 836 837 Author: [rivalq](/profile/rivalq "Master rivalq") 838 Idea: [rivalq](/profile/rivalq "Master rivalq") 839 840 **Editorial** 841 842 Tutorial is loading... 843 844 **Solution (rivalq)** 845 846 ``` 847 #include<bits/stdc++.h> 848 using namespace std; 849 850 #define rep(i,a,n) for(int i=a;i<n;i++) 851 #define ll long long 852 //#define int long long 853 #define pb push_back 854 #define all(v) v.begin(),v.end() 855 #define endl "\n" 856 #define x first 857 #define y second 858 #define gcd(a,b) __gcd(a,b) 859 #define mem1(a) memset(a,-1,sizeof(a)) 860 #define mem0(a) memset(a,0,sizeof(a)) 861 #define sz(a) (int)a.size() 862 #define pii pair<int,int> 863 #define hell 1000000007 864 #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 865 866 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;} 867 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;} 868 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;} 869 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;} 870 871 const int N = 5e4+5; 872 873 struct node{ 874 int a=0; 875 node (int val=0){ 876 a=val; 877 } 878 void merge(node &n1,node &n2){ 879 this->a=min(n1.a,n2.a); 880 } 881 }; 882 struct update{ 883 int val=0; 884 update(int t=0){ 885 val=t; 886 } 887 void combine(update &par,int tl,int tr){ 888 val+=par.val; 889 } 890 void apply(node &node){ 891 node.a+=val; 892 val=0; 893 } 894 }; 895 template<typename node,typename update> 896 struct segtree{ 897 node t[4*N]; 898 bool lazy[4*N]; 899 update zaker[4*N]; 900 int tl[4*N]; 901 int tr[4*N]; 902 node nul; 903 inline void pushdown(int v){ 904 if(lazy[v]){ 905 apply(zaker[v],v); 906 lazy[v]=0; 907 zaker[v].apply(t[v]); 908 } 909 } 910 inline void apply(update &u,int v){ 911 if(tl[v]!=tr[v]){ 912 lazy[2*v]=lazy[2*v+1]=1; 913 zaker[2*v].combine(u,tl[2*v],tr[2*v]); 914 zaker[2*v+1].combine(u,tl[2*v+1],tr[2*v+1]); 915 } 916 } 917 void build(int v,int start,int end,int arr[]){ 918 tl[v]=start; 919 tr[v]=end; 920 lazy[v]=0; 921 zaker[v].val = 0; 922 if(start==end){ 923 t[v].a=arr[start]; 924 } 925 else{ 926 int m=(start+end)/2; 927 build(2*v,start,m,arr); 928 build(2*v+1,m+1,end,arr); 929 t[v].merge(t[2*v],t[2*v+1]); 930 } 931 } 932 void zeno(int v,int l,int r,update val){ 933 pushdown(v); 934 if(tr[v]<l || tl[v]>r)return; 935 if(l<=tl[v] && tr[v]<=r){ 936 t[v].a+=val.val; 937 apply(val,v); 938 return; 939 } 940 zeno(2*v,l,r,val); 941 zeno(2*v+1,l,r,val); 942 t[v].merge(t[2*v],t[2*v+1]); 943 } 944 node query(int v,int l,int r){ 945 if(tr[v]<l || tl[v]>r)return node(hell); 946 pushdown(v); 947 if(l<=tl[v] && tr[v]<=r){ 948 return t[v]; 949 } 950 node a=query(2*v,l,r); 951 node b=query(2*v+1,l,r); 952 node ans; 953 ans.merge(a,b); 954 return ans; 955 } 956 public: 957 node query(int l,int r){ 958 return query(1,l,r); 959 } 960 void upd(int l,int r,update val){ 961 return zeno(1,l,r,val); 962 } 963 }; 964 965 segtree<node,update>seg; 966 967 int dp[101][N]; 968 969 int solve(){ 970 int n,k; cin >> n >> k; 971 vector<int>a(n+1); 972 rep(i,1,n+1){ 973 cin >> a[i]; 974 } 975 for(int i = 0; i <= n; i++){ 976 for(int j = 0; j <= k; j++){ 977 dp[j][i] = hell; 978 } 979 } 980 dp[0][0] = 0; 981 seg.build(1,0,n,dp[0]); 982 983 for(int j = 1; j <= k; j++){ 984 vector<int>last(n+1); 985 dp[j][0] = 0; 986 for(int i = 1; i <= n; i++){ 987 if(last[a[i]] == 0){ 988 last[a[i]] = i; 989 } 990 else{ 991 seg.upd(0,last[a[i]]-1,i-last[a[i]]); 992 last[a[i]] = i; 993 } 994 dp[j][i] = seg.query(0,i-1).a; 995 996 } 997 seg.build(1,0,n,dp[j]); 998 999 } 1000 cout << dp[k][n] << endl; 1001 //cout << elasped_time << endl; 1002 return 0; 1003 } 1004 signed main(){ 1005 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 1006 //freopen("test.txt", "r", stdin); 1007 //freopen("output.txt", "w", stdout); 1008 #ifdef SIEVE 1009 sieve(); 1010 #endif 1011 #ifdef NCR 1012 init(); 1013 #endif 1014 int t=1;//cin>>t; 1015 while(t--){ 1016 solve(); 1017 } 1018 return 0; 1019 } 1020 ``` 1021 1022 **Solution (the_nightmare)** 1023 1024 ``` 1025 #include<bits/stdc++.h> 1026 #include <ext/pb_ds/assoc_container.hpp> 1027 #include <ext/pb_ds/tree_policy.hpp> 1028 #define ll long long 1029 #define pb push_back 1030 #define ppb pop_back 1031 #define endl '\n' 1032 #define mii map<ll,ll> 1033 #define msi map<string,ll> 1034 #define mis map<ll, string> 1035 #define rep(i,a,b) for(ll i=a;i<b;i++) 1036 #define repr(i,a,b) for(ll i=b-1;i>=a;i--) 1037 #define trav(a, x) for(auto& a : x) 1038 #define pii pair<ll,ll> 1039 #define vi vector<ll> 1040 #define vii vector<pair<ll, ll>> 1041 #define vs vector<string> 1042 #define all(a) (a).begin(),(a).end() 1043 #define F first 1044 #define S second 1045 #define sz(x) (ll)x.size() 1046 #define hell 1000000007 1047 #define lbnd lower_bound 1048 #define ubnd upper_bound 1049 #define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl; 1050 #define display(x) trav(a,x) cout<<a<<" ";cout<<endl; 1051 #define what_is(x) cerr << #x << " is " << x << endl; 1052 #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 1053 #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 1054 using namespace __gnu_pbds; 1055 using namespace std; 1056 #define PI 3.141592653589793 1057 #define MAXN 35005 1058 int tree1[4*MAXN]; 1059 int lazy[4*MAXN]; 1060 int s[MAXN]; 1061 void build(int node, int start, int end) 1062 { 1063 lazy[node]=0; 1064 if(start == end) 1065 { 1066 // Leaf node will have a single element 1067 tree1[node] = s[start]; 1068 //cout << tree1[node] << " "; 1069 } 1070 else 1071 { 1072 int mid = (start + end) / 2; 1073 // Recurse on the left child 1074 build(2*node, start, mid); 1075 // Recurse on the right child 1076 build(2*node+1, mid+1, end); 1077 // Internal node will have the sum of both of its children 1078 tree1[node] = min(tree1[2*node],tree1[2*node+1]); 1079 } 1080 } 1081 void updateRange(int node, int start, int end, int l, int r, int val) 1082 { 1083 if (l>r) return; 1084 if(lazy[node] != 0) 1085 { 1086 // This node needs to be updated 1087 tree1[node] = tree1[node]+lazy[node]; // Update it 1088 if(start != end) 1089 { 1090 lazy[node*2] += lazy[node]; // Mark child as lazy 1091 lazy[node*2+1] += lazy[node]; // Mark child as lazy 1092 } 1093 lazy[node] = 0; // Reset it 1094 } 1095 if(start > end or start > r or end < l) // Current segment is not within range [l, r] 1096 return; 1097 if(start >= l and end <= r) 1098 { 1099 // Segment is fully within range 1100 tree1[node] = tree1[node]+val; 1101 if(start != end) 1102 { 1103 // Not leaf node 1104 lazy[node*2] += val; 1105 lazy[node*2+1] += val; 1106 } 1107 return; 1108 } 1109 int mid = (start + end) / 2; 1110 updateRange(node*2, start, mid, l, r, val); // Updating left child 1111 updateRange(node*2 + 1, mid + 1, end, l, r, val); // Updating right child 1112 tree1[node] = min(tree1[node*2],tree1[node*2+1]); // Updating root with max value 1113 } 1114 1115 ll queryRange(int node, int start, int end, int l, int r) 1116 { 1117 if(start > end or start > r or end < l) 1118 return hell; // Out of range 1119 if(lazy[node] != 0) 1120 { 1121 // This node needs to be updated 1122 tree1[node] = tree1[node]+lazy[node]; // Update it 1123 if(start != end) 1124 { 1125 lazy[node*2] += lazy[node]; // Mark child as lazy 1126 lazy[node*2+1] += lazy[node]; // Mark child as lazy 1127 } 1128 lazy[node] = 0; // Reset it 1129 } 1130 if(start >= l and end <= r) // Current segment is totally within range [l, r] 1131 return tree1[node]; 1132 int mid = (start + end) / 2; 1133 ll p1 = queryRange(node*2, start, mid, l, r); // Query left child 1134 ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child 1135 return min(p1,p2); 1136 } 1137 void solve() 1138 { 1139 ll n,k; 1140 cin >> n >> k; 1141 int a[n]; 1142 rep(i,0,n) cin >> a[i]; 1143 int lastoc[n]; 1144 map <int,int> m1; 1145 rep(i,0,n){ 1146 if (m1.find(a[i])==m1.end()) lastoc[i]=-1; 1147 else lastoc[i]=m1[a[i]]; 1148 m1[a[i]]=i; 1149 } 1150 int dp[n][k+1]; 1151 dp[0][1]=0; 1152 rep(i,1,n){ 1153 dp[i][1]=dp[i-1][1]; 1154 if (lastoc[i]!=-1) dp[i][1]+=i-lastoc[i]; 1155 } 1156 rep(i,2,k+1){ 1157 rep(j,0,n) s[j]=dp[j][i-1]; 1158 build(1,0,n-1); 1159 rep(j,0,i-1) dp[j][i]=hell; 1160 dp[i-1][i]=0; 1161 rep(j,i,n) 1162 { 1163 int lastj=lastoc[j]; 1164 if (lastj>0 and (i-2)<(lastj)) { 1165 updateRange(1,0,n-1,i-2,lastj-1,j-lastj); 1166 } 1167 dp[j][i] = queryRange(1,0,n-1,i-2,j-1); 1168 } 1169 } 1170 cout << dp[n-1][k] << endl; 1171 } 1172 int main() 1173 { 1174 #ifndef ONLINE_JUDGE 1175 freopen ("input.txt","r",stdin); 1176 #endif 1177 ll int TEST=1; 1178 //cin >> TEST; 1179 //init(); 1180 while(TEST--) 1181 { 1182 solve(); 1183 } 1184 } 1185 1186 } 1187 ```