2272.md (26609B)
1 Source: https://codeforces.com/blog/entry/158188 2 3 #### [2272A - Maximize One MEX](/contest/2272/problem/A "Codeforces Round 1130 (Div. 2)") 4 5 Idea: [yvbf](/profile/yvbf "Master yvbf"), Preparation: [yvbf](/profile/yvbf "Master yvbf") 6 7 **Solution** 8 9 $f_i$ is defined as the $\operatorname{mex}$ of the prefix subarray of $a$. According to the definition of $\operatorname{mex}$, it is obvious that $f_i \le f_{i+1}$. Therefore, the $k$-th largest value among $f_1, f_2, \ldots, f_n$ can be regarded as $f_{n-k+1}$. Then the original problem is equivalent to swapping two values in the sequence $a$ at most once so that $f_{n-k+1}$ is maximized, i.e., maximizing $\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})$. 10 11 Let initially $v=\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})$. Then swapping two numbers that are both located in $range_1=[1,n-k+1]$, or both located in $range_2=(n-k+1,n]$, will not change the value of $v$. If the two swapped numbers are respectively in the above two intervals, the optimal solution is obviously to swap the value $v$ from $range_2$ to $range_1$, so that after the swap we can obtain $\operatorname{mex}(a_1,a_2,\ldots,a_{n-k+1})\geq v+1$, provided that the number removed from $range_1$ is greater than $v$. 12 13 By the definition of $\operatorname{mex}$, $v$ is the minimum value in $range_2$. Then a simple method is to choose the maximum value $x$ from $range_1$ and the minimum value $y$ from $range_2$. If $x \gt y$, swap the two; if $x \lt y$, it means $range_1$ contains all numbers from $0$ to $v-1$, so not swapping is the optimal solution. 14 15 Time complexity: $O(n)$ 16 17 **Code** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 23 int main() { 24 ios::sync_with_stdio(false); 25 cin.tie(nullptr); 26 int t; 27 cin >> t; 28 while (t--) { 29 int n, k; 30 cin >> n >> k; 31 vector<int> a(n); 32 for (int i = 0; i < n; i++) cin >> a[i]; 33 34 if (k == 1) { 35 cout << -1 << '\n'; 36 } else { 37 auto x = max_element(a.begin(), a.begin() + n - k + 1) - a.begin(); 38 auto y = min_element(a.begin() + n - k + 1, a.end()) - a.begin(); 39 if (a[x] > a[y]) { 40 cout << x + 1 << ' ' << y + 1 << '\n'; 41 } else { 42 cout << -1 << '\n'; 43 } 44 } 45 } 46 return 0; 47 } 48 ``` 49 50 **Rate the Problem!** 51 52 * Heat 53 * Mid 54 * Horrendous 55 * Didn't Solve 56 57 #### [2272B - Frogs Jump](/contest/2272/problem/B "Codeforces Round 1130 (Div. 2)") 58 59 Idea: [yvbf](/profile/yvbf "Master yvbf"), Preparation: [yvbf](/profile/yvbf "Master yvbf") 60 61 **Solution** 62 63 First, let us consider several simplest cases with only two frogs: 64 65 1. If the cells containing the two frogs share an edge, i.e., they are adjacent horizontally or vertically, then they can jump to each other's positions respectively, thereby keeping the total number of frogs in each row and each column required by the problem unchanged. 66 2. If the cells containing the two frogs share a cell vertex, i.e., they are diagonally adjacent, then the frog on the left can jump to the right, and the frog on the right can jump to the left, thereby keeping the total number of frogs in each row and each column required by the problem unchanged. 67 68 Since every column in the given grid contains at least one frog, if the total number of frogs in the input is even, we can always select, from left to right, two frogs satisfying one of the above two cases, and make them jump according to the above method, thereby satisfying the requirements of the problem. 69 70 If the total number of frogs in the input is odd, there is no valid solution that keeps the total number of frogs in each row and each column required by the problem unchanged. We assume that there is a valid solution. Since jumping left and right does not affect the total number of frogs in each row, the number of frogs jumping down and the number of frogs jumping up are obviously equal, and after these frogs jump they do not affect the total number of frogs in each column, and these frogs are even in number. Since the total number of frogs is odd, if we keep only the frogs that jump left and right in this solution, the total number of these frogs is odd, and the solution should still be valid. Since the total number of rows no longer matters, we can imagine that the grid becomes a single row, and each cell contains 1 or 2 frogs. Then consider all frogs at the leftmost side; they can only jump to the right, so the cell immediately to the right of this cell must contain an equal number of frogs jumping to the left, in order to keep the total number of frogs in each column unchanged. Since the total number of frogs is odd, one frog will remain in the end, and after jumping it will break the requirements of the problem. 71 72 Therefore, we obtain the final conclusion: when the total number of frogs is even, there is always a solution; when the total number is odd, it suffices to remove one frog so that the total number becomes even. 73 74 **Code** 75 76 ``` 77 #include <bits/stdc++.h> 78 using namespace std; 79 80 int main() { 81 std::ios::sync_with_stdio(false); 82 std::cin.tie(nullptr); 83 int t; 84 cin >> t; 85 while (t--) { 86 int n; 87 cin >> n; 88 string s1, s2; 89 cin >> s1 >> s2; 90 auto tot = ranges::count(s1, 'f') + ranges::count(s2, 'f'); 91 cout << tot % 2 << '\n'; 92 } 93 return 0; 94 } 95 ``` 96 97 **Rate the Problem!** 98 99 * Heat 100 * Mid 101 * Horrendous 102 * Didn't Solve 103 104 #### [2272C - Yet Another Black Cell Problem](/contest/2272/problem/C "Codeforces Round 1130 (Div. 2)") 105 106 Idea: [yvbf](/profile/yvbf "Master yvbf"), Preparation: [MaxBlazeIceInk](/profile/MaxBlazeIceInk "Master MaxBlazeIceInk") 107 108 **Solution** 109 110 Fix $k$. Operations only add black cells and each blacks exactly two cells at distance in $[1,k]$, so a final black set $B$ is achievable iff $B \supseteq a$, $|B| \le n+x$, and in the sorted order of $B$ every cell has a neighbor in $B$ at distance at most $k$: one operation per cell together with its partner paints exactly $B$. Adding cells only shrinks gaps, so extras never hurt. 111 112 Call $a_i$ bad if all its adjacent gaps in $a$ exceed $k$ (for the endpoints, the single gap). Non-bad cells already have a partner inside $a$; each bad cell needs one from the added set $S = B \setminus a$. One added cell $p$ serves at most two bad cells: if it served bad cells $a_i \lt a_j$ with $j \ge i+2$, the disjoint gaps $a_{i+1}-a_i$ and $a_j-a_{j-1}$, both exceeding $k$, lie inside $[a_i,a_j]$ and force $a_j-a_i \gt 2k$, contradicting $|p-a_i|,|p-a_j| \le k$. So only consecutive bad cells with $a_{i+1}-a_i \le 2k$ may share $p$, and both cases are realizable: $p=a_i+k$ lies strictly between two consecutive bad cells (hence $p \notin a$) and is within $k$ of both; $p=a_i+1$ serves a lone bad cell, and $p \notin a$ since every adjacent gap of a bad cell exceeds $k \ge 1$. 113 114 Hence the minimum $|S|$ equals the number of bad cells minus the maximum number of disjoint consecutive bad pairs with gap at most $2k$; this is a matching on a path, so the left-to-right greedy that pairs whenever possible is optimal, which is exactly what the check function computes. Thus $k$ is feasible iff this greedy count does not exceed $x$. 115 116 Feasibility is monotone in $k$, since all conditions above only relax as $k$ grows, and $k=10^9$ always works because then no cell is bad. Binary searching the minimum feasible $k$ on $[1,10^9]$ with an $O(n)$ check costs $O(n \log 10^9)$ per test case, well within the limits. 117 118 Time complexity: $O(n\log V)$ 119 120 **Code** 121 122 ``` 123 #include<bits/stdc++.h> 124 using namespace std; 125 126 typedef long long ll; 127 #define MAXN 200005 128 129 int n,x,lef[MAXN],a[MAXN]; 130 131 inline bool check( int d ){ 132 int c = 0; 133 for( int i = 1 ; i <= n ; i ++ ) lef[i] = 0; 134 for( int i = 1 ; i <= n ; i ++ ){ 135 int L = i == 1 || a[i] - a[i - 1] > d; 136 int R = i == n || a[i + 1] - a[i] > d; 137 lef[i] = L && R; 138 } 139 for( int i = 1 ; i <= n ; i ++ ){ 140 if( lef[i] ){ 141 if( i < n && lef[i + 1] ){ 142 if( a[i + 1] - a[i] <= 2 * d ) lef[i] = lef[i + 1] = 0,c ++; 143 else lef[i] = 0,c ++; 144 } 145 else{ 146 lef[i] = 0,c ++; 147 } 148 } 149 } 150 return c <= x; 151 } 152 153 inline void solve(){ 154 scanf("%d%d",&n,&x); 155 for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]); 156 int l = 1,r = (ll)1e9,ans = -1; 157 while( l <= r ){ 158 int mid = ( l + r ) >> 1; 159 if( check( mid ) ) ans = mid,r = mid - 1; 160 else l = mid + 1; 161 } 162 printf("%d\n",ans); 163 } 164 165 signed main(){ 166 int t; scanf("%d",&t); 167 while( t -- ) solve(); 168 return 0; 169 } 170 ``` 171 172 **Rate the Problem!** 173 174 * Heat 175 * Mid 176 * Horrendous 177 * Didn't Solve 178 179 #### [2272D - Connecting the Conflicts](/contest/2272/problem/D "Codeforces Round 1130 (Div. 2)") 180 181 Idea: [yvbf](/profile/yvbf "Master yvbf"), Preparation: [yvbf](/profile/yvbf "Master yvbf"), [MaxBlazeIceInk](/profile/MaxBlazeIceInk "Master MaxBlazeIceInk") 182 183 **Solution** 184 185 First, if the original graph has no edges, then choosing a center vertex and adding an edge from every other vertex to this center is clearly an optimal solution, yielding a maximum independent set of size $n−1$. 186 187 If the original graph does contain edges, then for a tree that is a connected component with at least one edge, take a vertex $u$ adjacent to some leaf. This vertex $u$ is necessarily not in some maximum independent set. For every other connected component of the original graph, arbitrarily choose one vertex and connect it to $u$. This yields an independent set whose size is the same as the maximum independent set of the original graph. Since the maximum independent set size of the resulting tree cannot exceed that of the original graph before adding edges, the tree constructed in this way is one of the optimal solutions. 188 189 Time Complexity: $O(n)$. 190 191 **Code** 192 193 ``` 194 #include<bits/stdc++.h> 195 using namespace std; 196 197 int main() { 198 int t; 199 cin >> t; 200 while (t--) { 201 int k; 202 cin >> k; 203 vector<vector<vector<int>>> trees(k); 204 for (int i = 0; i < k; i++) { 205 int n; 206 cin >> n; 207 trees[i].assign(n, {}); 208 for (int j = 0; j < n - 1; j++) { 209 int x, y; 210 cin >> x >> y; 211 x--, y--; 212 trees[i][x].push_back(y); 213 trees[i][y].push_back(x); 214 } 215 } 216 217 int ri = -1, rj = -1; 218 for (int i = 0; i < k && ri == -1; i++) { 219 if (trees[i].size() > 1) { 220 for (int j = 0; j < trees[i].size() && ri == -1; j++) { 221 if (trees[i][j].size() == 1) { 222 ri = i, rj = trees[i][j][0]; 223 } 224 } 225 } 226 } 227 if (ri == -1) ri = rj = 0; 228 for (int i = 0; i < k; i++) { 229 if (i == ri) continue; 230 cout << i + 1 << " 1 " << ri + 1 << " " << rj + 1 << "\n"; 231 } 232 } 233 return 0; 234 } 235 ``` 236 237 **Rate the Problem!** 238 239 * Heat 240 * Mid 241 * Horrendous 242 * Didn't Solve 243 244 #### [2272E - Memory Cell Interception](/contest/2272/problem/E "Codeforces Round 1130 (Div. 2)") 245 246 Idea: [yvbf](/profile/yvbf "Master yvbf"), Preparation: [MaxBlazeIceInk](/profile/MaxBlazeIceInk "Master MaxBlazeIceInk") 247 248 **Solution** 249 250 Consider a single `R` in $s$ at position $i$. There are two cases. 251 252 **Case 1: there is a `W` in front of this `R`.** Let $j$ be the index of the nearest such `W`. It is not hard to see that, by inserting $t$, we can make the answer take every value in $[j, j+m]$, where $m = |t|$. Clearly the answer can never be smaller than $i$, but it can be larger. Now look at the last occurrence of `W` in $t$ (say it is the $k$-th character of $t$): we may read it last, and then the answer can also reach $i-1+k$. This part is contiguous as well, so the set of attainable answers is exactly the interval $[j, \max(j+m, i-1+k)]$. 253 254 **Case 2: there is no `W` in front of this `R`.** Then $0$ is attainable, and we can compute the answer directly. Take a `W` of $t$ at position $j$; it lets $[j, j+i-1]$ be absorbed into the answer interval. Hence the answer is the size of the union of all intervals $[j, j+i-1]$. 255 256 To get the answer for every `R`, iterate over $i$ from left to right; then all these intervals grow simultaneously. We maintain the number of currently alive intervals, and for each of them the moment at which it catches up with the next interval; at those moments we subtract its contribution and retire it. 257 258 Complexity: $O(n+m)$. 259 260 **Code** 261 262 ``` 263 #include<bits/stdc++.h> 264 using namespace std; 265 266 #define MAXN 400005 267 268 int len[2],f[2],g[2],difs[MAXN]; 269 char s[2][MAXN],t[MAXN]; 270 271 inline void Getans( int id ){ 272 int g = 0,cnt = 0; 273 for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) g = i,cnt ++; 274 vector<int> A,dif; 275 for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) A.emplace_back( i ); 276 for( int i = 0 ; i + 1 < (int)A.size() ; i ++ ) difs[A[i + 1] - A[i] - 1] ++; 277 if( g ) difs[len[0] + len[1]] ++; 278 for( int i = len[0] + len[1] - 1 ; i >= 0 ; i -- ) difs[i] += difs[i + 1]; 279 for( int i = 1 , c = 0 ; i <= len[id] ; i ++ ){ 280 if( s[id][i] == 'R' ){ 281 if( !c ){ 282 printf("%d ",cnt + 1); 283 cnt += difs[i]; 284 } 285 else{ 286 int L = c; 287 int R = max( c + len[id ^ 1] , g ? i - 1 + g : 0 ); 288 printf("%d ",R - L + 1); 289 } 290 } 291 else c = i; 292 } 293 for( int i = 0 ; i <= len[0] + len[1] ; i ++ ) difs[i] = 0; 294 puts(""); 295 } 296 297 inline void solve(){ 298 scanf("%d%d%s%s",&len[0],&len[1],s[0] + 1,s[1] + 1); 299 Getans( 0 ),Getans( 1 ); 300 } 301 302 signed main(){ 303 int t; scanf("%d",&t); 304 while( t -- ) solve(); 305 return 0; 306 } 307 ``` 308 309 **Rate the Problem!** 310 311 * Heat 312 * Mid 313 * Horrendous 314 * Didn't Solve 315 316 #### [2272F - Tree Reduction Game](/contest/2272/problem/F "Codeforces Round 1130 (Div. 2)") 317 318 Idea: [JerrySyr](/profile/JerrySyr "Master JerrySyr"), Preparation: [JerrySyr](/profile/JerrySyr "Master JerrySyr") 319 320 **Hint1** 321 322 If we choose a child of the current root as the new root, do the vertices outside that child's subtree still matter? 323 324 **Hint2** 325 326 We can consider that, on the next move, we simply delete all vertices that were outside that subtree. The only difference is that this effectively adds one extra operation: passing one turn. 327 328 **Hint3** 329 330 This suggests a tree DP solution. However, we certainly cannot run a separate tree DP for every possible choice of root. So what should we do? 331 332 **Hint4** 333 334 Use rerooting DP. 335 336 **Solution** 337 338 We use rerooting DP to determine the winner for every possible initial root. 339 340 First, define two types of game states: 341 342 * $f(u,p)$: The current root is $u$, and the state is obtained by rerooting from $p$ to $u$. The direction toward $p$ is no longer available, and the current player has one extra Pass. The value is $1$ if the current player wins, and $0$ otherwise. 343 * $g(u)$: The current root is $u$, and no extra Pass is available. The value is $1$ if the current player wins, and $0$ otherwise. 344 345 If Bob chooses vertex $r$ as the initial root, Alice starts from state $g(r)$. 346 347 Our goal is to compute $g(u)$ for every vertex $u$ in $O(n)$ time. 348 349 ### 1. DP Definitions 350 351 Choose vertex $1$ as an arbitrary temporary root. 352 353 For each vertex $u$, define 354 355 $ down[u] = f(u,parent(u)). $ 356 357 For each non-root vertex $u$, define 358 359 $ up[u] = f(parent(u),u). $ 360 361 Also, let 362 363 $ h(u) = \sum_{v \in child(u)} [down[v]=0]. $ 364 365 In other words, $h(u)$ is the number of children whose corresponding $f$-states are losing. 366 367 ### 2. Computing down[u] 368 369 Let $c$ be the number of children of $u$. 370 371 In state $f(u,parent(u))$, the current player has one extra Pass. 372 373 There are two cases: 374 375 * If $h(u) \gt 0$, there exists a child $v$ such that $down[v]=0$. The current player can move the root to $v$ and leave a losing state to the opponent. Therefore, $down[u]=1$. 376 * Otherwise, all children have winning states. In this case, the result is determined by the parity of the number of available directions and the extra Pass. The current player wins exactly when $c$ is even. 377 378 Thus, 379 380 $ down[u]=1 \iff h(u) \gt 0 \lor c\bmod 2=0. $ 381 382 In particular, if $u$ is a leaf, then $c=0$, so $down[u]=1$. 383 384 We can compute all $down[u]$ and $h(u)$ using a bottom-up DFS. 385 386 ### 3. Computing up[v] 387 388 Consider a child $v$ of vertex $u$. We need to compute 389 390 $ up[v]=f(u,v). $ 391 392 In this state, the current root is $u$, the extra Pass is available, and the direction toward $v$ is excluded. 393 394 The state is losing if and only if all of the following conditions hold: 395 396 1. The parent direction does not lead to a losing state. This is automatically satisfied if $u$ is the temporary root. Otherwise, we require $up[u]=1$. 397 2. None of the remaining children leads to a losing state. After excluding $v$, the number of losing child directions is $h(u)-[down[v]=0]$, which must be $0$. 398 3. The number of remaining available directions is odd, since an $f$-state without a losing next state is losing exactly under this parity condition. There are $deg(u)-1$ remaining directions, so we require $deg(u)$ to be even. 399 400 Combining these conditions gives 401 402 $ \begin{aligned} up[v]=0 \iff {}& (parent(u)=0 \lor up[u]=1)\\ &\land (h(u)-[down[v]=0]=0)\\ &\land (deg(u)\bmod 2=0). \end{aligned} $ 403 404 Since $up[v]$ depends only on information already computed at $u$, we can calculate all $up$ values using a top-down DFS. 405 406 ### 4. Computing g(u) 407 408 Now suppose $u$ is chosen as the initial root. 409 410 Unlike an $f$-state, the state $g(u)$ has no extra Pass, and all neighbors of $u$ are available. 411 412 The current player wins if at least one of the following conditions holds: 413 414 * Some child $v$ satisfies $down[v]=0$. 415 * The vertex $u$ has a parent, and $up[u]=0$. 416 * All neighboring directions lead to winning $f$-states, and $deg(u)$ is odd. 417 418 Therefore, 419 420 $ \begin{aligned} g(u)=1 \iff {}& h(u) \gt 0\\ &\lor (parent(u)\ne 0 \land up[u]=0)\\ &\lor (deg(u)\bmod 2=1). \end{aligned} $ 421 422 All the quantities required to evaluate $g(u)$ are now available. 423 424 ### 5. Algorithm 425 426 1. Root the tree at vertex $1$. 427 2. Run a bottom-up DFS to compute $down[u]$ and $h(u)$ for every vertex. 428 3. Run a top-down DFS to compute $up[u]$ for every non-root vertex. 429 4. Evaluate $g(u)$ for every vertex using the derived formula. 430 5. If there exists a vertex $r$ with $g(r)=0$, Bob can choose $r$ as the initial root and win. Otherwise, Alice wins regardless of Bob's choice. 431 432 ### 6. Complexity Analysis 433 434 Each DFS visits every vertex and edge a constant number of times. Each DP transition takes $O(1)$ time after the required information has been computed. 435 436 Therefore, the total time complexity is $O(n)$. 437 438 The adjacency lists and DP arrays require $O(n)$ space, so the total space complexity is also $O(n)$. 439 440 **Code** 441 442 ``` 443 #include <bits/stdc++.h> 444 using namespace std; 445 446 void solve() 447 { 448 int n; 449 cin >> n; 450 451 vector<vector<int>> e(n + 1); 452 for (int i = 1; i < n; i++) { 453 int u, v; 454 cin >> u >> v; 455 e[u].push_back(v); 456 e[v].push_back(u); 457 } 458 459 vector<int> fa(n + 1), order; 460 order.reserve(n); 461 462 fa[1] = 0; 463 order.push_back(1); 464 465 for (int i = 0; i < (int)order.size(); i++) { 466 int u = order[i]; 467 for (int v : e[u]) { 468 if (v == fa[u]) continue; 469 fa[v] = u; 470 order.push_back(v); 471 } 472 } 473 474 vector<int> down(n + 1), up(n + 1); 475 476 for (int i = n - 1; i >= 1; i--) { 477 int u = order[i]; 478 479 int lose = 0; 480 for (int v : e[u]) { 481 if (fa[v] == u && down[v] == 0) 482 lose++; 483 } 484 485 int child_cnt = (int)e[u].size() - 1; 486 487 down[u] = (lose > 0 || child_cnt % 2 == 0); 488 } 489 490 vector<int> lose_cnt(n + 1); 491 492 for (int u : order) { 493 int cnt = 0; 494 495 if (fa[u] && up[u] == 0) 496 cnt++; 497 498 for (int v : e[u]) { 499 if (fa[v] == u && down[v] == 0) 500 cnt++; 501 } 502 503 lose_cnt[u] = cnt; 504 505 for (int v : e[u]) { 506 if (fa[v] != u) continue; 507 508 int cur = cnt - (down[v] == 0); 509 510 up[v] = (cur > 0 || ((int)e[u].size() - 1) % 2 == 0); 511 } 512 } 513 514 vector<int> ans; 515 516 for (int u = 1; u <= n; u++) { 517 bool win = (lose_cnt[u] > 0 || (int)e[u].size() % 2 == 1); 518 519 if (!win) 520 ans.push_back(u); 521 } 522 523 if (ans.empty()) { 524 cout << "Alice\n"; 525 return; 526 } 527 528 cout << "Bob\n"; 529 cout << ans.size() << '\n'; 530 531 for (int i = 0; i < (int)ans.size(); i++) { 532 if (i) cout << ' '; 533 cout << ans[i]; 534 } 535 cout << '\n'; 536 } 537 538 int main() 539 { 540 ios::sync_with_stdio(false); 541 cin.tie(nullptr); 542 543 int T; 544 cin >> T; 545 546 while (T--) 547 solve(); 548 549 return 0; 550 } 551 ``` 552 553 **Rate the Problem!** 554 555 * Heat 556 * Mid 557 * Horrendous 558 * Didn't Solve 559 560 #### [2272G - Ranges](/contest/2272/problem/G "Codeforces Round 1130 (Div. 2)") 561 562 Idea: [MoScenix](/profile/MoScenix "Expert MoScenix"), Preparation: [MoScenix](/profile/MoScenix "Expert MoScenix") 563 564 **Solution** 565 566 Represent an interval $[l,r]$ by a directed edge 567 568 $ l\to r+1. $ 569 570 If we know the reports for $[l,k]$ and $[k+1,r]$, then we have 571 572 $ l\to k+1\to r+1, $ 573 574 so combining reports is exactly concatenating directed paths. Therefore, after making some direct queries, the report for $[l,r]$ can be obtained iff there is a directed path from $l$ to $r+1$. 575 576 Now consider the graph formed by the required intervals, but ignore edge directions: for every required $[l,r]$, add an undirected edge 577 578 $ \{l,r+1\}. $ 579 580 Suppose one connected component contains $s$ distinct vertices. We claim that its contribution to the answer is exactly 581 582 $ s-1. $ 583 584 First, at least $s-1$ queries are necessary. For every required edge, its two endpoints must be connected by the queried intervals, so all vertices of this component must belong to the same connected component after ignoring directions. Connecting $s$ vertices requires at least $s-1$ edges. 585 586 Using additional vertices or connecting several required components together cannot improve this bound: if a connected component of queried edges contains $s$ relevant vertices coming from $k$ required components, then it contains at least $s-1$ queried edges, while those required components contribute only $s-k \le s-1$. 587 588 The bound is also achievable. Sort all vertices of one component: 589 590 $ x_1 \lt x_2 \lt \dots \lt x_s. $ 591 592 Query 593 594 $ [x_1,x_2-1],\ [x_2,x_3-1],\dots,[x_{s-1},x_s-1]. $ 595 596 These queries form the directed path 597 598 $ x_1\to x_2\to\dots\to x_s. $ 599 600 For every required interval $[l,r]$, both $l$ and $r+1$ are vertices of this component and $l \lt r+1$, so the path contains a directed subpath from $l$ to $r+1$. Hence its report can be obtained. 601 602 Therefore, for every configuration, 603 604 $ \text{answer}=\sum_C(|C|-1) $ 605 606 This is exactly the number of successful merges when inserting all edges $(l,r+1)$ into a DSU. 607 608 The only remaining difficulty is that every modification deletes one old edge and inserts a new one. We process all modifications offline. Each version of an interval is active on one continuous range of times, so we add these active ranges to a segment tree over time and traverse it with a rollback DSU. 609 610 At every leaf, the DSU contains exactly the edges present in that configuration. Thus the number of successful unions is the required answer. 611 612 No path compression should be used in the rollback DSU; union by size is sufficient. 613 614 Let $V$ be the number of different values among all $l$ and $r+1$. We may coordinate-compress them, so $V=O(m+q)$. There are $O(m+q)$ different interval versions, and each is stored in $O(\log(q+1))$ segment-tree nodes. 615 616 The total complexity is 617 618 $ O((m+q)\log(q+1)\log V) $ 619 620 time and 621 622 $ O((m+q)\log(q+1)+V) $ 623 624 memory. 625 626 **Code** 627 628 ``` 629 #pragma GCC optimize("O2") 630 #include <bits/stdc++.h> 631 #include <numeric> 632 using namespace std; 633 #define int long long 634 #define i64 int64_t 635 #define db long double 636 #define pii pair<int, int> 637 #define tiii tuple<int, int, int> 638 #define ull unsigned long long 639 #define vi vector<int> 640 using i128 = __int128; 641 #define vpii vector<pii> 642 #define vvpii vector<vector<pii>> 643 #define vvi vector<vi> 644 #define pqpii priority_queue<pii, vector<pii>, greater<pii>> 645 #define pqi priority_queue<int, vi, greater<int>> 646 #define f first 647 #define s second 648 #define all(x) (x).begin(), (x).end() 649 #define pb push_back 650 #define eb emplace_back 651 #define sz(x) (x).size() 652 #define mp make_pair 653 #define endl '\n' 654 const int mod = 998244353; 655 const int INF = 1e18; 656 const int N = 5e5 + 5; 657 658 struct DSU { 659 vi fa; 660 vector<array<int, 4>> stk; 661 662 DSU(int n) : fa(n, -1) {} 663 664 int find(int x) { 665 while (fa[x] >= 0) 666 x = fa[x]; 667 return x; 668 } 669 670 void merge(int x, int y) { 671 x = find(x), y = find(y); 672 if (x == y) 673 return; 674 if (-fa[x] < -fa[y]) 675 swap(x, y); 676 stk.pb({x, y, fa[x], fa[y]}); 677 fa[x] += fa[y]; 678 fa[y] = x; 679 } 680 681 int snap() { 682 return (int)sz(stk); 683 } 684 685 void rollback(int p) { 686 while ((int)sz(stk) > p) { 687 auto [x, y, fx, fy] = stk.back(); 688 stk.pop_back(); 689 fa[x] = fx; 690 fa[y] = fy; 691 } 692 } 693 694 int rank() { 695 return (int)sz(stk); 696 } 697 }; 698 699 struct qy { 700 int l, r; 701 pii e; 702 }; 703 704 void init() {} 705 706 void solve() { 707 int n, m, q; 708 cin >> n >> m >> q; 709 710 vpii cur(m); 711 for (auto &[l, r] : cur) { 712 cin >> l >> r; 713 ++r; 714 } 715 716 vector<tiii> upd(q); 717 for (auto &[p, l, r] : upd) { 718 cin >> p >> l >> r; 719 --p, ++r; 720 } 721 722 vi st(m, 0); 723 vector<qy> evt; 724 evt.reserve(m + q); 725 726 for (int t = 1; t <= q; t++) { 727 auto [p, l, r] = upd[t - 1]; 728 evt.pb({st[p], t, cur[p]}); 729 cur[p] = {l, r}; 730 st[p] = t; 731 } 732 for (int i = 0; i < m; i++) 733 evt.pb({st[i], q + 1, cur[i]}); 734 735 int tot = q + 1, base = 1; 736 while (base < tot) 737 base <<= 1; 738 vvpii seg(base << 1); 739 740 auto add = [&](int l, int r, pii e) { 741 for (l += base, r += base; l < r; l >>= 1, r >>= 1) { 742 if (l & 1) 743 seg[l++].pb(e); 744 if (r & 1) 745 seg[--r].pb(e); 746 } 747 }; 748 749 for (auto [l, r, e] : evt) 750 add(l, r, e); 751 752 DSU dsu(n + 2); 753 vi ans(tot); 754 755 auto dfs = [&](auto &&self, int u) -> void { 756 int p = dsu.snap(); 757 for (auto [x, y] : seg[u]) 758 dsu.merge(x, y); 759 760 if (u >= base) { 761 int t = u - base; 762 if (t < tot) 763 ans[t] = dsu.rank(); 764 } else { 765 self(self, u << 1); 766 self(self, u << 1 | 1); 767 } 768 dsu.rollback(p); 769 }; 770 771 dfs(dfs, 1); 772 for (int x : ans) 773 cout << x << endl; 774 } 775 776 signed main() { 777 ios::sync_with_stdio(false); 778 cin.tie(nullptr); 779 780 init(); 781 782 int t = 1; 783 cin >> t; 784 while (t--) 785 solve(); 786 787 return 0; 788 } 789 ``` 790 791 **Rate the Problem!** 792 793 * Heat 794 * Mid 795 * Horrendous 796 * Didn't Solve