Once the winner of the first match is decided, the rest of the game is completely predictable.

For example, if Sosai wins the first match which Fofo spectated, we can see that:

No matter who wins in the second match, Hohai won't be able to continue playing in the third match (even if he wins the second match) since he has already played two times in a row. Similarly, Fofo won't be able to play in the fourth match because he has already played twice in a row, regardless of the match result.

As a result, Fofo won't be able to spectate in the $$$k$$$-th match for any $$$k$$$ of the form $$$3x + 1$$$.

The overall time complexity is: $$$O(1)$$$.

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int k;
    cin >> k;
    if (k % 3 == 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

The first observation is that if the sum $$$1 + 2 + … + n = \frac{n(n+1)}{2}$$$ is a perfect square, no valid perfect permutation exists.

To prove that a solution always exists otherwise, start with the identity permutation $$$p_i = i$$$ and iterate through indices from $$$1$$$ to $$$n$$$. We keep on iterating as long as the prefix sum till that moment isn’t a perfect square. If the prefix sum up to index $$$k$$$ becomes a perfect square, $$$\frac{k(k+1)}{2} = x^2$$$, swap $$$p_k$$$ and $$$p_{k + 1}$$$. This changes the prefix sum to $$$x^2 + 1$$$, which is not a perfect square.

To ensure this method works, we must show that $$$\frac{(k+1)(k+2)}{2}$$$ cannot also be a perfect square. Assume for contradiction that $$$\frac{(k+1)(k+2)}{2} = y^2$$$. Then:

Since $$$x > \frac{k}{2}$$$ (because $$$x^2 = \frac{k(k+1)}{2} > \frac{k^2}{4}$$$), we have:

which is a contradiction. Thus, $$$\frac{(k+1)(k+2)}{2}$$$ cannot be a perfect square, and the process can be repeated until all indices are processed, ensuring a valid permutation.

The overall time complexity is: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
void solve() {
    auto check = [&](int k) {
        int j = sqrtl((int64_t)k * (k + 1) / 2);
        return ((int64_t)j * j != (int64_t)k * (k + 1) / 2);
    };
    int n;
    cin >> n;
    if (!check(n)) {
        cout << "-1\n";
        return;
    }
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        ans[i] = i;
    }
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while ((int64_t)j * j < (int64_t)i * (i + 1) / 2) j++;
        if ((int64_t)j * j == (int64_t)i * (i + 1) / 2) {
            swap(ans[i], ans[i + 1]);
        }
        cout << ans[i] << " ";
    }
    cout << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

First, root the tree at vertex $$$\textrm{en}$$$ and approach it step by step. Observe that after processing all vertices at the largest depth $$$n−1$$$, the mouse’s current depth cannot exceed $$$n−1$$$. By repeating this process for the next largest depth $$$n−2$$$, the mouse’s depth will inevitably become $$$n−2$$$ or less. Continuing this way, we process vertices in descending order of depth until we reach the root, achieving the desired result.

The overall time complexity is: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n, s, e;
    cin >> n >> s >> e;
    vector adj(n + 1, vector<int> ());
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    vector dis(n + 1, vector<int> ());
    vector<int> d(n + 1);
    auto dfs = [&](auto &&self, int v, int par) -> void {
        d[v] = d[par] + 1;
        dis[d[v]].push_back(v);
        for (int u: adj[v]) {
            if (u == par) continue;
            self(self, u, v);
        }
    };
    dfs(dfs, e, 0);
    for (int i = n; i >= 1; i--) {
        for (int j: dis[i]) {
            cout << j << " ";
        }
    }
    cout << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

For convenience, assume $$$n$$$ is odd (if not, increment $$$n$$$ and handle the edge case separately). Start by precomputing the first $$$2n$$$ terms $$$a_1, a_2, \ldots, a_{2n}$$$. For queries with indices less than or equal to $$$2n$$$, directly return the precomputed value. For $$$2m>n$$$, observe the following relationship

Define $$$p = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$. Notice that when $$$m > n$$$, we can decompose the XOR sum as:

Since $$$n$$$ is odd, the pairs $$$(a_{n + 1} \oplus a_{n + 2}), (a_{n + 3} \oplus a_{n + 4}), \ldots$$$ cancel out. This simplifies the formula to:

As a result, we can compute $$$a_m$$$ recursively by halving $$$m$$$ until $$$m \le 2n$$$, applying the parity rule at each step.

The overall time complexity is: $$$O(\log(m))$$$.

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    int64_t l, r;
    cin >> n >> l >> r;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> pref(n + 1);
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }
    if (n % 2 == 0) {
        n++;
        int cur = pref[n / 2] & 1;
        a.push_back(cur);
        pref.push_back(pref.back() + cur);
    }
    for (int i = n + 1; i <= n * 2; i++) {
        a.push_back(pref[i / 2] & 1);
        pref.push_back(pref[i - 1] + a[i]);
    }
    int p = pref[n] & 1;
    auto get = [&](int64_t x) {
        int ret = 0;
        while (true) {
            if (x <= n * 2) {
                ret ^= a[x];
                break;
            }
            ret ^= p;
            if ((x / 2 - n) % 2 == 0) {
                break;
            }
            x /= 2;
        }
        return ret;
    };
    cout << get(l) << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

First, check the editorial of D1.

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    int64_t l, r;
    cin >> n >> l >> r;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> pref(n + 1);
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }
    if (n % 2 == 0) {
        n++;
        int cur = pref[n / 2] & 1;
        a.push_back(cur);
        pref.push_back(pref.back() + cur);
    }
    for (int i = n + 1; i <= n * 2; i++) {
        a.push_back(pref[i / 2] & 1);
        pref.push_back(pref[i - 1] + a[i]);
    }
    vector<int> even(n * 2 + 1);
    for (int i = 1; i <= n * 2; i++) {
        even[i] = even[i - 1] + (i & 1 ? 0 : a[i]);
    }
    int p = pref[n] & 1;
    auto get = [&](int64_t x) {
        int ret = 0;
        while (true) {
            if (x <= n * 2) {
                ret ^= a[x];
                break;
            }
            ret ^= p;
            if ((x / 2 - n) % 2 == 0) {
                break;
            }
            x /= 2;
        }
        return ret;
    };
    auto sum = [&](auto&& self, int64_t m) -> pair<int64_t, int64_t> {// {sum even, sum odd}
        if (m <= n * 2) {
            return {even[m], pref[m] - even[m]};
        }
        int64_t eve = even[n * 2 - 1], odd = pref[n * 2 - 1] - eve;
        if (m % 2 == 0) {
            m += 1, odd -= get(m);
        }
        if (m / 2 % 2) {
            m += 1, eve -= get(m);
            m += 1, odd -= get(m);
        }
        auto [e, _] = self(self, m / 2);
        e -= even[n];
        int64_t c = m / 2 - n + 1, both = (p ? c - e : e);
        eve += both, odd += both;
        return {eve, odd};
    };
    int64_t ans = 0;
    auto [re, ro] = sum(sum, r);
    ans += re + ro;
    auto [le, lo] = sum(sum, l - 1);
    ans -= le + lo;
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Let $$$fall_{i} $$$ denote the probability that the $$$i$$$-th node falls. We partition the unordered pairs $$$(u,v)$$$ into three categories:

1. $$$u$$$ and $$$v$$$ are direct neighbors.
2. $$$u$$$ and $$$v$$$ share a common neighbor.
3. Pairs that do not satisfy the first two conditions.

Now, let us analyze the contribution of the first category to the final answer. For a pair $$$(u,v)$$$ of direct neighbors, both vertices become leaves if neither $$$u$$$ nor $$$v$$$ falls and if all of their other neighbors fall. Thus, the contribution of a specific pair $$$(u,v)$$$ is given by $$$ contribution(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v}} fall_{k}. $$$

The whole contribution of the first category is $$$\sum_{(u,v) \text{ are neighbors}} contribution1(u,v)$$$.

For the second category, $$$u$$$ and $$$v$$$ share a neighbor, so this shared neighbor must be the only one not falling among the neighbors of $$$u$$$ and $$$v$$$, and both $$$u$$$ and $$$v$$$ must also not fall. Therefore, the contribution for a pair $$$(u,v)$$$ in the second category is given by $$$ contribution2(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot (1 - fall_{s}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v,\, k \neq s }} fall_{k} $$$ where $$$s$$$ is the shared neighbour of $$$u$$$ and $$$v$$$.

The whole contribution of the second category is $$$\sum_{(u,v) \text{ share a neighbor}} contribution2(u,v)$$$

Moving to the third category: Here, $$$u$$$ and $$$v$$$ are neither direct neighbors nor do they share any common neighbor. In this case, the events that $$$u$$$ and $$$v$$$ become leaves are completely independent.

Define $$$leaf_{i} = (1 - fall_{i}) \cdot \prod_{c \text{ is a neighbor of } i} fall_{c}$$$ as the probability that vertex $$$i$$$ becomes a leaf. Hence, for a pair $$$(u,v)$$$ in this category, the contribution is given by $$$ contribution3(u,v) = leaf_{u} \cdot leaf_{v}$$$.

The whole contribution of the third category is then $$$\sum_{(u,v) \in \text{third category}} contribution3(u,v)$$$.

The final answer is obtained by summing the contributions from all three categories. We can compute the contribution of the third category by summing $$$leaf_{i} \cdot leaf_{j}$$$ for all pairs $$$(i, j)$$$ with $$$i < j$$$, and then subtracting the contributions corresponding to pairs that satisfy one of the first two categories. The contribution of the second category can be computed by iterating over each node and accumulating the contributions from its neighbors (since these pairs share that node as their only common neighbor). The contribution of the first category can be computed in linear time too.

The overall time complexity is $$$O(n \cdot \log M)$$$, where the $$$\log$$$ factor arises from the modular inverse computations.

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int add(int x, int y) {
    return x + y - (x + y >= mod) * mod;
}
void add2(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
int mul(int x, int y) {
    return int((int64_t)x * y % mod);
}
int sub(int x, int y) {
    return x - y + (x < y) * mod;
}
void sub2(int &x, int y) {
    x -= y;
    if (x < 0) x += mod;
}
int pwr(int x, int y) {
    int ret = 1;
    while (y) {
        if (y & 1) ret = mul(ret, x);
        x = mul(x, x);
        y /= 2;
    }
    return ret;
}
int inv(int x) {
    return pwr(x, mod - 2);
}
int norm(int64_t x) {
    x %= mod;
    if (x < 0) x += mod;
    return int(x);
}
void solve() {
    int n;
    cin >> n;
    vector adj(n + 1, vector<int> ());
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        int q;
        cin >> p[i] >> q;
        p[i] = mul(p[i], inv(q));
        //here, p[i] is the probability that node i will fall
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    vector<int> p1(n + 1), p2(n + 1);
    for (int i = 1; i <= n; i++) {
        p1[i] = sub(1, p[i]);
        for (int u: adj[i]) {
            p1[i] = mul(p1[i], p[u]);
        }
        //p1[i] is the probability that node i won't fall, but all nodes around it will fall
        for (int u: adj[i]) {
            add2(p2[i], mul(p1[i], mul(inv(p[u]), sub(1, p[u]))));
        }
        //p2[i] is the probability that node i will be a leaf (it won't fall, all it's neighbors except one will fall)
    }
    int ans = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        add2(ans, mul(p2[i], sum));
        add2(sum, p2[i]);
    }
    //take all contributions of unordered pairs 
    for (int i = 1; i <= n; i++) {
        //recalculate the contribution of neighboring pairs 
        for (auto u: adj[i]) {
            if (u < i) continue;
            //avoid calculating the same pair probabilty twice
            int pi = mul(p1[i], inv(p[u]));
            //pi is the probability that every neighbour of i would fall except for u (not including the probability of u not falling down)
            int pu = mul(p1[u], inv(p[i]));
            //pu is the probability that every neighbour of u would fall except for i (not including the probability of i not falling down)
            //this case is just a tree of 2 nodes, both of them are leaves
            add2(ans, mul(pi, pu));
            //subtract the old contribution
            sub2(ans, mul(p2[i], p2[u]));
        }
        //recalculate the contribution of pairs with a shared neighbour which is node i (ie calculate the contribution for pairs u, v such that dis(u, v) = 2 and dis(u, i) = dis(v, i) = 1
        sum = 0;
        for (int u: adj[i]) {
            sub2(ans, mul(sum, p2[u]));
            add2(sum, p2[u]);
            //subtract the old contribution 
        }
        //p[i] doesn't fall
        sum = 0;
        for (int u: adj[i]) {
            int pu = mul(p1[u], inv(p[i]));
            //pu is the probability that node u is a leaf connected to node i
            add2(ans, mul(sum, pu));
            add2(sum, mul(pu, sub(1, p[i])));
        }
        //p[i] falls
        sum = 0;
        for (int u: adj[i]) {
            int pu = sub(p2[u], mul(p1[u], mul(inv(p[i]), sub(1, p[i]))));
            //pu is the probability that node u is a leaf not connected to node i
            add2(ans, mul(sum, pu));
            add2(sum, mul(pu, inv(p[i])));
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Let's do binary search on $$$p$$$. After fixing some $$$p$$$ our goal is to find the maximum $$$p$$$-towering subsequence and check if the length of that subsequence $$$s$$$ satisfies $$$n - s \le k$$$.

To find the maximum p-towering subsequence, for each index $$$i$$$ we will find the maximum $$$p$$$-towering subsequence such that the "left" part of that subsequence is in prefix $$$i$$$ and its right part is in suffix $$$i$$$.

Let's focus only on prefixes, as the suffixes can be done similarly. So, for each prefix $$$i$$$ we want to find the maximum "increasing" $$$p$$$-towering subsequence. To do it, we will traverse the array from left to right and maintain the currently found maximum subsequence. The key idea here is that as you move from left to right you only need to add new elements to the "increasing" subsequence and never delete any (or, formally speaking, if we denote the set of indexes that correspond to maximum "increasing" $$$p$$$-towering subsequence on prefix $$$i$$$ as $$$S_i$$$, then for any $$$i < n$$$: $$$S_i \subseteq S_{i + 1}$$$ (the proof is left to the reader).

So we need some way to find such "new" numbers that appear when we add some elements to the subsequence (like when the element with value $$$5$$$ becomes available from the example). To resolve this we first assign $$$a_i := p - a_i$$$ for each $$$i$$$. To find the positions that are becoming available, we can search for the rightmost non-positive element on the current prefix. Once found (suppose its index is $$$j$$$), decrease all elements on the prefix $$$j$$$ by one and assign $$$a_j := \infty$$$ (to avoid this position in the future). All these operations can be performed with the help of a segment tree.

This concludes the asymptotic complexity: $$$O(n \log{C} \log{n})$$$.

#include <bits/stdc++.h>

#define len(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;
const int MAXI = 1e9 + 1e7;

const int MAXN = 2e5 + 100;
struct Node {
    int min_on_subtree = 0, push_addition = 0;
};
Node t[MAXN * 4];
int a[MAXN], pref[MAXN], suf[MAXN];

class Segtree {
private:
    int n;
    void add_on_subtree(int u, int val) {
        t[u].push_addition += val;
        t[u].min_on_subtree += val;
    }
    void push(int u) {
        if (t[u].push_addition) {
            add_on_subtree(u * 2 + 1, t[u].push_addition);
            add_on_subtree(u * 2 + 2, t[u].push_addition);
            t[u].push_addition = 0;
        }
    }
    void recalc(int u) {
        t[u].min_on_subtree = min(t[u * 2 + 1].min_on_subtree, t[u * 2 + 2].min_on_subtree);
    }
    void update(int u, int l, int r, int pos, int val) {
        if (l == r) {
            t[u].min_on_subtree = val;
        } else {
            push(u);
            int mid = (l + r) / 2;
            if (pos <= mid)
                update(u * 2 + 1, l, mid, pos, val);
            else
                update(u * 2 + 2, mid + 1, r, pos, val);
            recalc(u);
        }
    }
    void add_on_segment(int u, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr)
            add_on_subtree(u, val);
        else {
            push(u);
            int mid = (l + r) / 2;
            if (ql <= mid)
                add_on_segment(u * 2 + 1, l, mid, ql, qr, val);
            if (qr > mid)
                add_on_segment(u * 2 + 2, mid + 1, r, ql, qr, val);
            recalc(u);
        }
    }
    int find_prev_non_pos_put_inf(int u, int l, int r, int pos) {
        if (t[u].min_on_subtree > 0)
            return -1;
        if (l == r) {
            t[u].min_on_subtree = MAXI;
            return l;
        }
        push(u);
        int mid = (l + r) / 2, res = -1;
        if (pos > mid)
            res = find_prev_non_pos_put_inf(u * 2 + 2, mid + 1, r, pos);
        if (res == -1)
            res = find_prev_non_pos_put_inf(u * 2 + 1, l, mid, pos);
        recalc(u);
        return res;
    }
public:
    explicit Segtree(int n): n(n) {
        fill(t, t + 4 * n, Node{MAXI, 0});
    };

    void update(int pos, int val) {
        update(0, 0, n - 1, pos, val);
    }
    void add_on_segment(int ql, int qr, int val) {
        add_on_segment(0, 0, n - 1, ql, qr, val);
    }
    int find_prev_non_pos_put_inf(int pos) {
        return find_prev_non_pos_put_inf(0, 0, n - 1, pos);
    }
};

void f(int n, int p, int *res) {
    Segtree tree(n);
    int cur_sz = 0;
    for (int i = 0; i < n; i++) {
        tree.update(i, p - a[i]);
        int pos = i;
        while ((pos = tree.find_prev_non_pos_put_inf(pos)) != -1) {
            cur_sz++;
            tree.add_on_segment(0, pos, -1);
        }
        res[i] = cur_sz;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int testcases;
    cin >> testcases;
    while (testcases--) {
        int n, k;
        cin >> n >> k;
        int max_a = -1;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            max_a = max(max_a, a[i]);
        }
        int l = 0, r = max_a + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            f(n, mid, pref);
            reverse(a, a + n);
            f(n, mid, suf);
            reverse(a, a + n);
            reverse(suf, suf + n);
            int mx = -1;
            for (int i = 0; i < n; i++) {
                if (a[i] >= mid)
                    mx = max(mx, pref[i] + suf[i] - 1);
            }
            if (n - mx <= k)
                l = mid;
            else
                r = mid;
        }
        cout << l << '\n';
    }
}