codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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