2063.md (20587B)
1 Source: https://codeforces.com/blog/entry/138593 2 3 **Rating Predictions** 4 5 | Handles | A | B | C | D | E | F1 | F2 | 6 | --- | --- | --- | --- | --- | --- | --- | --- | 7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1000 | 1500 | 2200 | 2400 | 1800 | 2600 | 8 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 1100 | 1500 | 2100 | 2300 | 1800 | 2700 | 9 | [redpanda](/profile/redpanda "Expert redpanda") | 800 | 900 | 1400 | 2000 | 2400 | | | 10 | [larush](/profile/larush "Expert larush") | 800 | 1100 | 1600 | 2100 | | | | 11 | [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") | 800 | 900 | 1500 | 2000 | 2400 | 1800 | 2500 | 12 | [priyanshu.p](/profile/priyanshu.p "Master priyanshu.p") | 800 | 1200 | 1500 | 2000 | 2500 | 2000 | | 13 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 1000 | 1400 | 2000 | 2200 | 2000 | 2600 | 14 | [redheadphone](/profile/redheadphone "Candidate Master redheadphone") | 800 | 1200 | 1400 | 2000 | | | | 15 | [beaten_by_ai](/profile/beaten_by_ai "Expert beaten_by_ai") | 800 | 1100 | 1500 | 2100 | 2100 | 2000 | 2500 | 16 | [Mukundan314](/profile/Mukundan314 "Candidate Master Mukundan314") | 800 | 1000 | 1600 | 2000 | 2300 | 1900 | 2400 | 17 | [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once") | 800 | 1000 | 1500 | 1900 | 2200 | 1900 | 2400 | 18 | [ProofByContradiction_](/profile/ProofByContradiction_ "Expert ProofByContradiction_") | 800 | 1100 | 1500 | 2000 | 2300 | | | 19 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 1100 | 1500 | 1900 | 2400 | 1800 | 2500 | 20 | [temporary1](/profile/temporary1 "Master temporary1") | 800 | 1000 | 1500 | 2100 | 2300 | 2000 | 2600 | 21 | [cry](/profile/cry "International Master cry") | 800 | 1200 | 1400 | 2100 | 2300 | | | 22 | | | | | | | | | 23 | **Average** | 800 | 1060 | 1486.67 | 2033.33 | 2315.38 | 1900 | 2533.33 | 24 | **Average (Round)** | 800 | 1100 | 1500 | 2000 | 2300 | 1900 | 2500 | 25 | **Median** | 800 | 1100 | 1500 | 2000 | 2300 | 1900 | 2500 | 26 27 The editorial for each task is written by me, [chromate00](/profile/chromate00 "Expert chromate00"). I tried to explain each task with as much detail I could fit in. Brace yourselves, it is going to be LONG. Please don't try to open all spoilers at once, it lagged my browser. Also, I apologize for not telling you strongly enough to read every problem, almost every tester thought F1 is easy if you read it well... 28 29 Also, our fellow [wuhudsm](/profile/wuhudsm "Master wuhudsm") told me there will be another community contest in the Gym soon, details will be posted on <https://codeforces.com/blog/entry/138706> shortly :catThink: 30 31 **UPD**: Added solution codes to all solutions. 32 33 --- 34 35 ## [2063A - Minimal Coprime](/contest/2063/problem/A "Codeforces Round 1000 (Div. 2)") 36 37 Author: [chromate00](/profile/chromate00 "Expert chromate00") 38 39 **Hint** 40 41 Well, we gave you enough hints in the examples. I believe you can already guess it. 42 43 **Editorial** 44 45 Tutorial is loading... 46 47 **Code (Python)** 48 49 ``` 50 for i in range(int(input())): 51 x,y=map(int,input().split()) 52 if x==y==1: 53 print(1) 54 else: 55 print(y-x) 56 ``` 57 58 ## [2063B - Subsequence Update](/contest/2063/problem/B "Codeforces Round 1000 (Div. 2)") 59 60 Author: [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once") 61 62 **Hint** 63 64 Assume that you chose some two indices $i$ and $j$ included in the subsequence, such that $i \lt l$ and $j \gt r$. Does this actually help decrease the answer in any way? 65 66 **Editorial** 67 68 Tutorial is loading... 69 70 **Code (Python)** 71 72 ``` 73 import sys 74 input=lambda:sys.stdin.readline().rstrip() 75 76 for _ in range(int(input())): 77 n,l,r=map(int,input().split());l-=1 78 arr=[*map(int,input().split())] 79 brr=arr[:l]+sorted(arr[l:]) 80 crr=sorted(arr[:r])[::-1]+arr[r:] 81 print(min(sum(brr[l:r]),sum(crr[l:r]))) 82 ``` 83 84 ## [2063C - Remove Exactly Two](/contest/2063/problem/C "Codeforces Round 1000 (Div. 2)") 85 86 Author: [chromate00](/profile/chromate00 "Expert chromate00") 87 88 **Hint** 89 90 The answer after choosing two vertices is decided by the degrees of the two vertices, **and whether the two vertices are adjacent**. Can you find a clean solution where you don't have to care about the latter? 91 92 **Big Hint** 93 94 Sure, you can do DP on tree, but that's not what we want you to use. Think easier. 95 96 **Editorial** 97 98 Tutorial is loading... 99 100 **Code (Python, Approach 1)** 101 102 ``` 103 import sys 104 input=lambda:sys.stdin.readline().rstrip() 105 for i in range(int(input())): 106 n=int(input()) 107 deg=[0]*n 108 adj=[[] for i in range(n)] 109 for i in range(n-1): 110 u,v=map(int,input().split()) 111 u-=1;v-=1 112 deg[u]+=1 113 deg[v]+=1 114 adj[u].append(v) 115 adj[v].append(u) 116 ans=1 117 mans=0 118 sdeg=sorted(deg) 119 for i in range(n): 120 ans=deg[i] 121 ideg=[] 122 for v in adj[i]: 123 ideg.append(deg[v]) 124 ideg.append(deg[i]) 125 ideg.sort(reverse=True) 126 rem=[] 127 mx=-1 128 for d in ideg: 129 if sdeg[-1]==d: 130 sdeg.pop() 131 rem.append(d) 132 rem.reverse() 133 if sdeg: 134 mx=max(mx,sdeg[-1]) 135 for v in adj[i]: 136 mx=max(mx,deg[v]-1) 137 for d in rem: 138 sdeg.append(d) 139 mans=max(ans+mx-1,mans) 140 print(mans) 141 ``` 142 143 ## [2063D - Game With Triangles](/contest/2063/problem/D "Codeforces Round 1000 (Div. 2)") 144 145 Author: [wuhudsm](/profile/wuhudsm "Master wuhudsm") (Original Idea) & [chromate00](/profile/chromate00 "Expert chromate00") (Modified Idea) 146 147 **Hint** 148 149 The maximum score $g(x_a,x_b)$ after performing $x_a$ times with two points on $y=0$, and $x_b$ times with two points on $y=2$, can be easily computed in $\mathcal{O}(1)$ time. But naively checking all possible number of operations takes $\mathcal{O}(nm)$ time. Is there a property we can abuse so that we can solve for each $k$ faster? 150 151 **Big Hint** 152 153 $g(x_a,x_b)$ is a function consisting of two prefix sums, each for a **strictly decreasing** sequence. 154 155 **Editorial** 156 157 Tutorial is loading... 158 159 **Code (C++)** 160 161 ``` 162 #include<bits/stdc++.h> 163 using namespace std; 164 using ll=long long; 165 166 int main() 167 { 168 cin.tie(0)->sync_with_stdio(0); 169 int t;cin>>t; 170 while(t--) 171 { 172 int n,m;cin>>n>>m; 173 vector<ll>arr(n),brr(m); 174 for(ll&i:arr)cin>>i; 175 for(ll&i:brr)cin>>i; 176 sort(begin(arr),end(arr)); 177 sort(begin(brr),end(brr)); 178 vector<ll>asum(n+2),bsum(m+2); 179 for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(arr[n-i]-arr[i-1]); 180 for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(brr[m-i]-brr[i-1]); 181 vector<ll>ans{0}; 182 // maximize asum[ka]+bsum[kb] 183 // s.t. ka+kb = x 184 // ka*2+kb <= n -> ka*2+(x-ka) <= n -> ka+x <= n -> ka <= n-x 185 // ka+kb*2 <= m -> ka+2*(x-ka) <= m -> 2*x-ka <= m -> ka >= 2*x-m 186 // ka >= 0, x-ka >= 0 187 for(int x=1;2*x-m<=n-x;x++) 188 { 189 ll L=max(0,2*x-m),R=min(x,n-x); 190 if(L>R)break; 191 auto f=[&](int ka){return asum[ka]+bsum[x-ka];}; 192 while(R-L>3) 193 { 194 ll mL=(L*2+R)/3,mR=(L+R*2)/3; 195 if(f(mL)>f(mR))R=mR; 196 else L=mL; 197 } 198 ll mans=0; 199 for(int i=L;i<=R;i++) 200 { 201 mans=max(mans,f(i)); 202 } 203 ans.push_back(mans); 204 } 205 int kmax=(int)size(ans)-1; 206 cout<<kmax<<"\n"; 207 for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax]; 208 } 209 } 210 ``` 211 212 ## [2063E - Triangle Tree](/contest/2063/problem/E "Codeforces Round 1000 (Div. 2)") 213 214 Author: [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once") 215 216 **Hint** 217 218 When $(u,v)$ is a good pair, $f(u,v)$ is actually simply represented as follows. 219 220 $f(u,v)=2 \cdot \min(\text{dist}(u,\text{lca}),\text{dist}(v,\text{lca}))-1$ 221 222 Naively calculating this for all good pairs takes $\mathcal{O}(n^2)$ time. Can you find a different representation where we can count wiser? 223 224 **Editorial** 225 226 Tutorial is loading... 227 228 **Code (C++)** 229 230 ``` 231 #include<bits/stdc++.h> 232 using namespace std; 233 using ll=long long; 234 235 int main() 236 { 237 cin.tie(0)->sync_with_stdio(0); 238 int t;cin>>t; 239 while(t--) 240 { 241 ll n;cin>>n; 242 vector<ll>d(n,0),s(n),dc(n),dcs; 243 vector<vector<ll>>adj(n); 244 for(int i=1;i<n;i++) 245 { 246 int u,v;cin>>u>>v; 247 u--;v--; 248 adj[u].push_back(v); 249 adj[v].push_back(u); 250 } 251 auto dfs1=[&](auto dfs1,int v,int p=-1)->void 252 { 253 dc[d[v]]++; 254 ll sz=1; 255 for(int w:adj[v])if(w!=p) 256 { 257 d[w]=d[v]+1; 258 dfs1(dfs1,w,v); 259 sz+=s[w]; 260 } 261 s[v]=sz; 262 }; 263 dfs1(dfs1,0); 264 dcs=dc; 265 for(int i=n-2;i>=0;i--)dcs[i]+=dcs[i+1]; 266 ll ans=0,ans2=0; 267 auto dfs2=[&](auto dfs2,int v,int p=-1)->void 268 { 269 // v is min 270 ans+=2*d[v]*(dcs[d[v]]-s[v]); 271 // v is lca 272 ll subcnt=s[v]-1,lcnt=0; 273 for(int w:adj[v])if(w!=p) 274 { 275 lcnt+=(subcnt-s[w])*s[w]; 276 dfs2(dfs2,w,v); 277 } 278 ans2+=(2*d[v]+1)*(lcnt/2); 279 }; 280 dfs2(dfs2,0); 281 for(int i=0;i<n;i++) 282 { 283 ans2+=i*dc[i]*(dc[i]-1); 284 } 285 cout<<ans-ans2<<"\n"; 286 } 287 } 288 ``` 289 290 ## [2063F1 - Counting Is Not Fun (Easy Version)](/contest/2063/problem/F1 "Codeforces Round 1000 (Div. 2)") 291 292 Author: [chromate00](/profile/chromate00 "Expert chromate00") 293 294 **Hint** 295 296 The subproblem where you find the number of different balanced bracket sequences of length $2k$ is already well-known. 297 298 Now recall everyone's favorite data structure to solve problems related to balanced bracket sequences — **the stack**! 299 300 **Editorial** 301 302 Tutorial is loading... 303 304 **Code (C++)** 305 306 ``` 307 #include<bits/stdc++.h> 308 using namespace std; 309 using ll=long long; 310 const ll md=998244353; 311 312 int main() 313 { 314 int t;cin>>t; 315 vector<ll>ctl(5050); 316 ctl[0]=1; 317 for(int n=1;n<5050;n++) 318 { 319 for(int i=1;i<=n;i++) 320 { 321 ctl[n]=(ctl[n]+ctl[i-1]*ctl[n-i]%md)%md; 322 } 323 } 324 while(t--) 325 { 326 int n;cin>>n; 327 ll ans=ctl[n]; 328 cout<<ans<<" "; 329 string s(2*n+2,'.'); 330 s[0]='(';s[2*n+1]=')'; 331 for(int a=0;a<n;a++) 332 { 333 int i,j;cin>>i>>j; 334 ans=1; 335 s[i]='('; 336 s[j]=')'; 337 string stk; 338 for(char c:s) 339 { 340 if(c==')') 341 { 342 int cnt=0; 343 while(stk.back()!='(') 344 { 345 cnt++; 346 stk.pop_back(); 347 } 348 stk.pop_back(); 349 ans=(ans*ctl[cnt/2])%md; 350 } 351 else stk+=c; 352 } 353 cout<<ans<<" \n"[a+1==n]; 354 } 355 } 356 } 357 ``` 358 359 ## [2063F2 - Counting Is Not Fun (Hard Version)](/contest/2063/problem/F2 "Codeforces Round 1000 (Div. 2)") 360 361 Author: [chromate00](/profile/chromate00 "Expert chromate00") 362 363 **Hint** 364 365 In the solution of the easy subtask, we manually enumerated the minimal balanced subsequences, each time in $\mathcal{O}(n)$. 366 367 You can show that most minimal balanced subsequences do not change when a new clue is added. What data structure will you choose in order to utilize this fact as much as possible? 368 369 **Editorial** 370 371 Tutorial is loading... 372 373 **Code (C++)** 374 375 ``` 376 #include<bits/stdc++.h> 377 using namespace std; 378 using ll=long long; 379 const ll nil=-1; 380 const ll md=998244353; 381 382 ll pw(ll a,ll b) 383 { 384 ll c=1; 385 while(b>0) 386 { 387 if(b&1)c=c*a%md; 388 a=a*a%md; 389 b>>=1; 390 } 391 return c; 392 } 393 394 int main() 395 { 396 cin.tie(0)->sync_with_stdio(0); 397 vector<ll>fac(1010101,1),ctl(505050); 398 for(int i=1;i<1010101;i++)fac[i]=fac[i-1]*i%md; 399 for(int i=0;i<505050;i++) 400 { 401 ctl[i]=fac[i*2]*pw(fac[i]*fac[i+1]%md,md-2)%md; 402 } 403 ll t;cin>>t; 404 while(t--) 405 { 406 ll n;cin>>n; 407 vector<ll>L(n*2,nil),R(n*2,nil),P(n*2,nil),S(n*2); 408 auto update=[&](ll x) 409 { 410 S[x]=1; 411 if(L[x]!=nil)S[x]+=S[L[x]]; 412 if(R[x]!=nil)S[x]+=S[R[x]]; 413 }; 414 auto rotate=[&](ll x) 415 { 416 ll dummy; 417 ll p=P[x]; 418 ll b=nil; 419 if(p==nil)return; 420 if(x==L[p]) 421 { 422 L[p]=b=R[x]; 423 R[x]=p; 424 } 425 else 426 { 427 R[p]=b=L[x]; 428 L[x]=p; 429 } 430 P[x]=P[p];P[p]=x; 431 if(b!=nil)P[b]=p; 432 (P[x]!=nil?p==L[P[x]]?L[P[x]]:R[P[x]]:dummy)=x; 433 update(p);update(x); 434 }; 435 auto splay=[&](ll x) 436 { 437 while(P[x]!=nil) 438 { 439 ll p=P[x]; 440 ll g=P[p]; 441 if(g!=nil) 442 { 443 if((x==L[p])==(p==L[g]))rotate(p); 444 else rotate(x); 445 } 446 rotate(x); 447 } 448 }; 449 update(0); 450 for(int i=1;i<n*2;i++) 451 { 452 L[i]=i-1; 453 P[i-1]=i; 454 update(i); 455 } 456 splay(0); 457 ll ans=ctl[n]; 458 cout<<ans<<" "; 459 for(int i=0;i<n;i++) 460 { 461 ll li,ri;cin>>li>>ri; 462 //li=(li+ans%(2*n))%(2*n); 463 //ri=(ri+ans%(2*n))%(2*n); 464 li--;ri--; 465 splay(li); 466 ans=ans*pw(ctl[S[li]/2],md-2)%md; 467 ll lli=L[li]; 468 if(L[li]!=nil)P[L[li]]=nil; 469 if(R[li]!=nil)P[R[li]]=nil; 470 L[li]=nil; 471 R[li]=nil; 472 update(li); 473 // now L[li] separated from tree 474 // should not be affected in splay ri 475 splay(ri); 476 ll lri=L[ri]; 477 ll rri=R[ri]; 478 if(L[ri]!=nil)P[L[ri]]=nil; 479 if(R[ri]!=nil)P[R[ri]]=nil; 480 L[ri]=nil; 481 R[ri]=nil; 482 update(ri); 483 if(lri!=nil) 484 { 485 splay(lri); 486 ans=ans*ctl[S[lri]/2]%md; 487 } 488 if(lli!=nil&&rri!=nil) 489 { 490 while(L[rri]!=nil)rri=L[rri]; 491 splay(lli); 492 splay(rri); 493 P[lli]=rri; 494 L[rri]=lli; 495 update(rri); 496 ans=ans*ctl[S[rri]/2]%md; 497 } 498 else if(lli!=nil||rri!=nil) 499 { 500 if(lli!=nil) 501 { 502 splay(lli); 503 ans=ans*ctl[S[lli]/2]%md; 504 } 505 else 506 { 507 splay(rri); 508 ans=ans*ctl[S[rri]/2]%md; 509 } 510 } 511 L[ri]=li; 512 P[li]=ri; 513 update(ri); 514 // make dummy tree (for invariant maintaining) 515 cout<<ans<<" \n"[i+1==n]; 516 } 517 } 518 } 519 ``` 520 521 **UPD**: People pointed out that the intended solution in the tutorial is overkill. Yes, I acknowledge this. Please look into the newly added alternative solution if you want a more elegant idea. 522 523 **Editorial (Alternative)** 524 525 Consider maintaining the MBSes directly, but instead of using a complex data structure, we will use a small-to-large trick with linked lists. Precisely, every time we have to split a linked list, we will identify the smaller section and split it out in $\mathcal{O}(|small|)$ time, and then the amortized time complexity will be $\mathcal{O}(n \log n)$. In this solution, we do not consider bracket pairs as MBSes, for a specific reason. 526 527 Given a linked list of indices and two nodes on it, we can identify the smaller section in $\mathcal{O}(|small|)$ by iterating over both lists at the same time, interlacing the operations. The list which hit the end earlier will be the smaller one, and then we immediately know the value of $|small|$. 528 529 The issue is that you cannot identify the size of both lists in $\mathcal{O}(|small|)$ time. This is hard to fix using only a linked list. Instead, we will also maintain the implicit rooted tree structure of the bracket sequence. The MBSes correspond to vertices, and the bracket pairs correspond to edges. Initially, the tree just consists of one vertex of $2n$ brackets. 530 531 Now, for each list node, we add a pointer to the corresponding tree vertex. Now we can know which tree vertex the list node corresponds to immediately, and if we bookkeep size informations in the tree vertices, we can also find the sum of two list sizes in $\mathcal{O}(1)$. Therefore we can now know the size of both lists in $\mathcal{O}(|small|)$ time. 532 533 The only issue is with how to maintain the pointers to the tree vertices. But no problem, you can just do the small-to-large for this also. After splitting the tree vertex into two vertices and one edge, redirect the smaller list to the new smaller vertex. Theoretically there are enough ways to do this, such as swapping vertex indices. Also it is notable that it is not necessary to maintain the whole tree in this process, it is quite sufficient to just maintain it implicitly by just maintaining a sequence of sizes. 534 535 The problem is solved online with $\mathcal{O}(n \log n)$ amortized time complexity. 536 537 **Code (C++, by Mukundan314)** 538 539 ``` 540 #pragma GCC optimize("O3,unroll-loops") 541 542 #include <iostream> 543 #include <numeric> 544 #include <vector> 545 546 constexpr int MAX_N = 3e5; 547 constexpr long long MOD = 998244353; 548 549 struct _inv_small { 550 long long data[MAX_N + 2] = {0}; 551 constexpr _inv_small() { 552 data[1] = 1; 553 for (int i = 2; i <= MAX_N; i += 2) { 554 data[i] = MOD - (MOD / i) * data[MOD % i] % MOD; 555 data[i + 1] = MOD - (MOD / (i + 1)) * data[MOD % (i + 1)] % MOD; 556 } 557 } 558 }; 559 560 constexpr _inv_small __inv_small; 561 #define inv_small(x) __inv_small.data[x] 562 563 #define inv(x) (x < MAX_N ? inv_small(x) : data[(x) - MAX_N]) 564 struct _inv { 565 long long data[MAX_N + 3] = {0}; 566 constexpr _inv() { 567 for (int i = 0; i <= MAX_N + 1; i += 2) { 568 data[i] = MOD - (MOD / (i + MAX_N)) * inv(MOD % (i + MAX_N)) % MOD; 569 data[i + 1] = MOD - (MOD / (i + MAX_N + 1)) * inv(MOD % (i + MAX_N + 1)) % MOD; 570 } 571 } 572 }; 573 #undef inv 574 575 constexpr _inv __inv; 576 #define inv(x) (x < MAX_N ? inv_small(x) : __inv.data[(x) - MAX_N]) 577 578 struct _catalan { 579 long long data[MAX_N + 2] = {1}; 580 constexpr _catalan() { 581 for (int i = 1; i <= MAX_N; i += 2) { 582 data[i] = (4 * i - 2) * data[i - 1] % MOD * inv(i + 1) % MOD; 583 data[i + 1] = (4 * i + 2) * data[i] % MOD * inv(i + 2) % MOD; 584 } 585 } 586 }; 587 588 constexpr _catalan __catalan; 589 #define catalan(x) __catalan.data[x] 590 591 struct _catalan_inv { 592 long long data[MAX_N + 2] = {1}; 593 constexpr _catalan_inv() { 594 for (int i = 1; i <= MAX_N; i += 2) { 595 data[i] = inv(2) * inv(2 * i - 1) % MOD * data[i - 1] % MOD * (i + 1) % MOD; 596 data[i + 1] = inv(2) * inv(2 * i + 1) % MOD * data[i] % MOD * (i + 2) % MOD; 597 } 598 } 599 }; 600 601 constexpr _catalan_inv __catalan_inv; 602 #define catalan_inv(x) __catalan_inv.data[x] 603 604 int main() { 605 std::cin.tie(0)->sync_with_stdio(0); 606 607 int t; 608 std::cin >> t; 609 610 for (int _ = 0; _ < t; ++_) { 611 int n; 612 std::cin >> n; 613 614 std::vector<bool> used(2 * n + 2); 615 616 std::vector<int> point(2 * n + 2); 617 std::iota(point.begin(), point.end(), 1); 618 619 std::vector<int> size(2 * n + 2); 620 621 std::vector<int> parent = {0}; 622 std::vector<int> parent_idx(2 * n + 2); 623 624 used[0] = true; 625 point[0] = 2 * n + 2, point[2 * n + 1] = 2 * n + 1; 626 size[0] = 2 * n; 627 628 long long ans = catalan(n); 629 630 std::cout << ans << " "; 631 632 for (int i = 0, l, r; i < n; ++i) { 633 std::cin >> l >> r; 634 635 point[l] = r + 1, point[r] = r; 636 used[l] = true; 637 638 int p = parent[parent_idx[l]]; 639 640 int out_ptr = p + 1, ins_ptr = l + 1; 641 int out_size = 0, ins_size = 0; 642 643 while (point[out_ptr] != out_ptr && point[ins_ptr] != ins_ptr) { 644 out_size += !used[out_ptr]; 645 ins_size += !used[ins_ptr]; 646 out_ptr = point[out_ptr]; 647 ins_ptr = point[ins_ptr]; 648 } 649 650 ans = (ans * catalan_inv(size[p] / 2)) % MOD; 651 652 int upd_ptr; 653 if (point[out_ptr] == out_ptr) { 654 upd_ptr = p + 1; 655 parent.push_back(p); 656 parent[parent_idx[l]] = l; 657 658 ins_size = size[p] - 2 - out_size; 659 size[p] = out_size, size[l] = ins_size; 660 } else { 661 upd_ptr = l + 1; 662 parent.push_back(l); 663 664 out_size = size[p] - 2 - ins_size; 665 size[p] = out_size, size[l] = ins_size; 666 } 667 668 ans = (ans * catalan(size[p] / 2)) % MOD * catalan(size[l] / 2) % MOD; 669 670 while (point[upd_ptr] != upd_ptr) { 671 parent_idx[upd_ptr] = parent.size() - 1; 672 upd_ptr = point[upd_ptr]; 673 } 674 675 std::cout << ans << " "; 676 } 677 678 std::cout << '\n'; 679 } 680 } 681 ```