$$$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})$$$.

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$$$.

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.

Time complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        if (k == 1) {
            cout << -1 << '\n';
        } else {
            auto x = max_element(a.begin(), a.begin() + n - k + 1) - a.begin();
            auto y = min_element(a.begin() + n - k + 1, a.end()) - a.begin();
            if (a[x] > a[y]) {
                cout << x + 1 << ' ' << y + 1 << '\n';
            } else {
                cout << -1 << '\n';
            }
        }
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

First, let us consider several simplest cases with only two frogs:

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.

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.

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.

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.

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.

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        auto tot = ranges::count(s1, 'f') + ranges::count(s2, 'f');
        cout << tot % 2 << '\n';
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

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.

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$$$.

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$$$.

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.

Time complexity: $$$O(n\log V)$$$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MAXN 200005

int n,x,lef[MAXN],a[MAXN];

inline bool check( int d ){
	int c = 0;
	for( int i = 1 ; i <= n ; i ++ ) lef[i] = 0;
	for( int i = 1 ; i <= n ; i ++ ){
		int L = i == 1 || a[i] - a[i - 1] > d;
		int R = i == n || a[i + 1] - a[i] > d;
		lef[i] = L && R;
	}
	for( int i = 1 ; i <= n ; i ++ ){
		if( lef[i] ){
			if( i < n && lef[i + 1] ){
				if( a[i + 1] - a[i] <= 2 * d ) lef[i] = lef[i + 1] = 0,c ++;
				else lef[i] = 0,c ++;
			}
			else{
				lef[i] = 0,c ++;
			}
		}
	}
	return c <= x;
}

inline void solve(){
	scanf("%d%d",&n,&x);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);
	int l = 1,r = (ll)1e9,ans = -1;
	while( l <= r ){
		int mid = ( l + r ) >> 1;
		if( check( mid ) ) ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
}

signed main(){
	int t; scanf("%d",&t);
	while( t -- ) solve();
	return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

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$$$.

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.

Time Complexity: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        vector<vector<vector<int>>> trees(k);
        for (int i = 0; i < k; i++) {
            int n;
            cin >> n;
            trees[i].assign(n, {});
            for (int j = 0; j < n - 1; j++) {
                int x, y;
                cin >> x >> y;
                x--, y--;
                trees[i][x].push_back(y);
                trees[i][y].push_back(x);
            }
        }

        int ri = -1, rj = -1;
        for (int i = 0; i < k && ri == -1; i++) {
            if (trees[i].size() > 1) {
                for (int j = 0; j < trees[i].size() && ri == -1; j++) {
                    if (trees[i][j].size() == 1) {
                        ri = i, rj = trees[i][j][0];
                    }
                }
            }
        }
        if (ri == -1) ri = rj = 0;
        for (int i = 0; i < k; i++) {
            if (i == ri) continue;
            cout << i + 1 << " 1 " << ri + 1 << " " << rj + 1 << "\n";
        }
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Consider a single R in $$$s$$$ at position $$$i$$$. There are two cases.

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)]$$$.

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]$$$.

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.

Complexity: $$$O(n+m)$$$.

#include<bits/stdc++.h>
using namespace std;

#define MAXN 400005

int len[2],f[2],g[2],difs[MAXN];
char s[2][MAXN],t[MAXN];

inline void Getans( int id ){
	int g = 0,cnt = 0;
	for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) g = i,cnt ++;
	vector<int> A,dif;
	for( int i = 1 ; i <= len[id ^ 1] ; i ++ ) if( s[id ^ 1][i] == 'W' ) A.emplace_back( i );
	for( int i = 0 ; i + 1 < (int)A.size() ; i ++ ) difs[A[i + 1] - A[i] - 1] ++;
	if( g ) difs[len[0] + len[1]] ++;
	for( int i = len[0] + len[1] - 1 ; i >= 0 ; i -- ) difs[i] += difs[i + 1];
	for( int i = 1 , c = 0 ; i <= len[id] ; i ++ ){
		if( s[id][i] == 'R' ){
			if( !c ){
				printf("%d ",cnt + 1);
				cnt += difs[i];
			}
			else{
				int L = c;
				int R = max( c + len[id ^ 1] , g ? i - 1 + g : 0 );
				printf("%d ",R - L + 1);
			}
		}
		else c = i;
	}
	for( int i = 0 ; i <= len[0] + len[1] ; i ++ ) difs[i] = 0;
	puts("");
}

inline void solve(){
	scanf("%d%d%s%s",&len[0],&len[1],s[0] + 1,s[1] + 1);
	Getans( 0 ),Getans( 1 );
}

signed main(){
	int t; scanf("%d",&t);
	while( t -- ) solve();
	return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

If we choose a child of the current root as the new root, do the vertices outside that child's subtree still matter?

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.

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?

Use rerooting DP.

We use rerooting DP to determine the winner for every possible initial root.

First, define two types of game states:

• $$$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.
• $$$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.

If Bob chooses vertex $$$r$$$ as the initial root, Alice starts from state $$$g(r)$$$.

Our goal is to compute $$$g(u)$$$ for every vertex $$$u$$$ in $$$O(n)$$$ time.

1. DP Definitions

Choose vertex $$$1$$$ as an arbitrary temporary root.

For each vertex $$$u$$$, define

For each non-root vertex $$$u$$$, define

Also, let

In other words, $$$h(u)$$$ is the number of children whose corresponding $$$f$$$-states are losing.

2. Computing down[u]

Let $$$c$$$ be the number of children of $$$u$$$.

In state $$$f(u,parent(u))$$$, the current player has one extra Pass.

There are two cases:

• 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$$$.
• 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.

Thus,

In particular, if $$$u$$$ is a leaf, then $$$c=0$$$, so $$$down[u]=1$$$.

We can compute all $$$down[u]$$$ and $$$h(u)$$$ using a bottom-up DFS.

3. Computing up[v]

Consider a child $$$v$$$ of vertex $$$u$$$. We need to compute

In this state, the current root is $$$u$$$, the extra Pass is available, and the direction toward $$$v$$$ is excluded.

The state is losing if and only if all of the following conditions hold:

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$$$.
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$$$.
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.

Combining these conditions gives

Since $$$up[v]$$$ depends only on information already computed at $$$u$$$, we can calculate all $$$up$$$ values using a top-down DFS.

4. Computing g(u)

Now suppose $$$u$$$ is chosen as the initial root.

Unlike an $$$f$$$-state, the state $$$g(u)$$$ has no extra Pass, and all neighbors of $$$u$$$ are available.

The current player wins if at least one of the following conditions holds:

• Some child $$$v$$$ satisfies $$$down[v]=0$$$.
• The vertex $$$u$$$ has a parent, and $$$up[u]=0$$$.
• All neighboring directions lead to winning $$$f$$$-states, and $$$deg(u)$$$ is odd.

Therefore,

All the quantities required to evaluate $$$g(u)$$$ are now available.

5. Algorithm

1. Root the tree at vertex $$$1$$$.
2. Run a bottom-up DFS to compute $$$down[u]$$$ and $$$h(u)$$$ for every vertex.
3. Run a top-down DFS to compute $$$up[u]$$$ for every non-root vertex.
4. Evaluate $$$g(u)$$$ for every vertex using the derived formula.
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.

6. Complexity Analysis

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.

Therefore, the total time complexity is $$$O(n)$$$.

The adjacency lists and DP arrays require $$$O(n)$$$ space, so the total space complexity is also $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    vector<int> fa(n + 1), order;
    order.reserve(n);

    fa[1] = 0;
    order.push_back(1);

    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : e[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            order.push_back(v);
        }
    }

    vector<int> down(n + 1), up(n + 1);

    for (int i = n - 1; i >= 1; i--) {
        int u = order[i];

        int lose = 0;
        for (int v : e[u]) {
            if (fa[v] == u && down[v] == 0)
                lose++;
        }

        int child_cnt = (int)e[u].size() - 1;

        down[u] = (lose > 0 || child_cnt % 2 == 0);
    }

    vector<int> lose_cnt(n + 1);

    for (int u : order) {
        int cnt = 0;

        if (fa[u] && up[u] == 0)
            cnt++;

        for (int v : e[u]) {
            if (fa[v] == u && down[v] == 0)
                cnt++;
        }

        lose_cnt[u] = cnt;

        for (int v : e[u]) {
            if (fa[v] != u) continue;

            int cur = cnt - (down[v] == 0);

            up[v] = (cur > 0 || ((int)e[u].size() - 1) % 2 == 0);
        }
    }

    vector<int> ans;

    for (int u = 1; u <= n; u++) {
        bool win = (lose_cnt[u] > 0 || (int)e[u].size() % 2 == 1);

        if (!win)
            ans.push_back(u);
    }

    if (ans.empty()) {
        cout << "Alice\n";
        return;
    }

    cout << "Bob\n";
    cout << ans.size() << '\n';

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Represent an interval $$$[l,r]$$$ by a directed edge

If we know the reports for $$$[l,k]$$$ and $$$[k+1,r]$$$, then we have

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$$$.

Now consider the graph formed by the required intervals, but ignore edge directions: for every required $$$[l,r]$$$, add an undirected edge

Suppose one connected component contains $$$s$$$ distinct vertices. We claim that its contribution to the answer is exactly

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.

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$$$.

The bound is also achievable. Sort all vertices of one component:

Query

These queries form the directed path

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.

Therefore, for every configuration,

This is exactly the number of successful merges when inserting all edges $$$(l,r+1)$$$ into a DSU.

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.

At every leaf, the DSU contains exactly the edges present in that configuration. Thus the number of successful unions is the required answer.

No path compression should be used in the rollback DSU; union by size is sufficient.

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.

The total complexity is

time and

memory.

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;

struct DSU {
    vi fa;
    vector<array<int, 4>> stk;

    DSU(int n) : fa(n, -1) {}

    int find(int x) {
        while (fa[x] >= 0)
            x = fa[x];
        return x;
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)
            return;
        if (-fa[x] < -fa[y])
            swap(x, y);
        stk.pb({x, y, fa[x], fa[y]});
        fa[x] += fa[y];
        fa[y] = x;
    }

    int snap() {
        return (int)sz(stk);
    }

    void rollback(int p) {
        while ((int)sz(stk) > p) {
            auto [x, y, fx, fy] = stk.back();
            stk.pop_back();
            fa[x] = fx;
            fa[y] = fy;
        }
    }

    int rank() {
        return (int)sz(stk);
    }
};

struct qy {
    int l, r;
    pii e;
};

void init() {}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vpii cur(m);
    for (auto &[l, r] : cur) {
        cin >> l >> r;
        ++r;
    }

    vector<tiii> upd(q);
    for (auto &[p, l, r] : upd) {
        cin >> p >> l >> r;
        --p, ++r;
    }

    vi st(m, 0);
    vector<qy> evt;
    evt.reserve(m + q);

    for (int t = 1; t <= q; t++) {
        auto [p, l, r] = upd[t - 1];
        evt.pb({st[p], t, cur[p]});
        cur[p] = {l, r};
        st[p] = t;
    }
    for (int i = 0; i < m; i++)
        evt.pb({st[i], q + 1, cur[i]});

    int tot = q + 1, base = 1;
    while (base < tot)
        base <<= 1;
    vvpii seg(base << 1);

    auto add = [&](int l, int r, pii e) {
        for (l += base, r += base; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                seg[l++].pb(e);
            if (r & 1)
                seg[--r].pb(e);
        }
    };

    for (auto [l, r, e] : evt)
        add(l, r, e);

    DSU dsu(n + 2);
    vi ans(tot);

    auto dfs = [&](auto &&self, int u) -> void {
        int p = dsu.snap();
        for (auto [x, y] : seg[u])
            dsu.merge(x, y);

        if (u >= base) {
            int t = u - base;
            if (t < tot)
                ans[t] = dsu.rank();
        } else {
            self(self, u << 1);
            self(self, u << 1 | 1);
        }
        dsu.rollback(p);
    };

    dfs(dfs, 1);
    for (int x : ans)
        cout << x << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve