• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Easy contest
• Normal contest
• Hard contest

Without short steps, we can only visit coordinates where $$$x$$$ and $$$y$$$ are both even.

Using only long steps, we can only visit coordinates where $$$x \equiv 0 \pmod 2$$$ and $$$y \equiv 0 \pmod 2$$$. The extra short step allows us to change either $$$x$$$ or $$$y$$$ to become odd (i.e. $$$x \equiv 1 \pmod 2$$$ or $$$y \equiv 1 \pmod 2$$$), but not both.

Thus, we can say that all coordinates are reachable except for ones where both $$$x$$$ and $$$y$$$ are odd, since that would require more than one short step.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int x, y;
        cin >> x >> y;
        cout << (x % 2 == 0 || y % 2 == 0 ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

It can never be harmful to choose the entire string as the substring.

As mentioned in the hint, choosing the entire string to be the substring, that we perform the operation on, is always optimal. Let's assume a smaller substring yields a valid RBS, we can just choose the entire string, and only move around the characters which are in the smaller substring. Thus, choosing the entire string is always optimal.

Now, the problem reduces to checking if we can rearrange a bracket sequence to become an RBS. We want each '$$$\texttt{(}$$$' to pair with a '$$$\texttt{)}$$$', leaving no unpaired brackets. This is equivalent to checking whether the number of occurrences of '$$$\texttt{(}$$$' is equal to the number of occurrences of '$$$\texttt{)}$$$' in the string.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        int cnt = 0;
        for(int i = 0; i < n; i++) cnt += s[i] == '(';
 
        cout << (2 * cnt == n ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

A subarray should have both $$$2$$$ and $$$3$$$ as prime factors of the product to be divisible by $$$6$$$. Each element can either contribute $$$2$$$, or $$$3$$$, or both.

From the previous hint, we can split the elements into $$$4$$$ groups.

A subarray has product divisible by $$$6$$$ if it contains both $$$2$$$ and $$$3$$$ as prime factors. Therefore, every element falls into one of $$$4$$$ groups:

• $$$S_6$$$: Elements divisible by $$$6$$$
• $$$S_2$$$: Elements divisible by $$$2$$$ but not $$$3$$$
• $$$S_3$$$: Elements divisible by $$$3$$$ but not $$$2$$$
• $$$S_1$$$: Elements neither divisible by $$$2$$$ nor $$$3$$$

Elements in $$$S_6$$$ already make any subarray divisible by $$$6$$$, so we want them packed together at an end to minimize the number of subarrays they are included in. For the next 2 paragraphs, let's forget about $$$S_6$$$.

For the remaining elements, if we place all $$$S_2$$$ before all $$$S_3$$$, then the only divisible subarrays are the ones that start in $$$S_2$$$ and end in $$$S_3$$$. Any other order would only create more such subarrays.

What do we do with elements of $$$S_1$$$? Inserting them anywhere can never decrease the number of divisible subarrays, but we can avoid increasing by placing them between $$$S_2$$$ and $$$S_3$$$. Subarrays divisible by $$$6$$$ would still be ones that start in $$$S_2$$$ and end in $$$S_3$$$, so the number of divisible subarrays is still as minimal as possible.

Therefore, an optimal construction is:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a, b, c, d;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if(x % 6 == 0) a.push_back(x);
            else if(x % 2 == 0) b.push_back(x);
            else if(x % 3 == 0) c.push_back(x);
            else d.push_back(x);
        }

        vector<int> ans;
        for(auto it : a) ans.push_back(it);
        for(auto it : b) ans.push_back(it);
        for(auto it : d) ans.push_back(it);
        for(auto it : c) ans.push_back(it);
        
        for(int i = 0; i < n; i++) cout << ans[i] <<  " \n"[i == n - 1];
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The minimum answer is $$$1$$$, because a $$$0$$$ always exists, and we can take a $$$0$$$ individually as a palindromic subarray with $$$\operatorname{mex} = 1$$$.

Any valid subarray with a $$$\operatorname{mex} \gt 1$$$ will still contain at least one $$$0$$$. So we know the optimal subarray will always contain a $$$0$$$.

There are several valid approaches to this problem. Here, I will explain the intended approach.

We can claim that the optimal subarray will always contain the element $$$0$$$. This is because, if it did not contain $$$0$$$, then $$$\operatorname{mex} = 0$$$. But $$$\operatorname{mex} = 1$$$ can be achieved by considering a $$$0$$$ element as its own subarray (it is palindromic). So, the optimal subarray must always contain the element $$$0$$$.

This gives us only $$$3$$$ candidate centers to expand the palindrome from. Let $$$x$$$ be the position of the first $$$0$$$ in the array, and $$$y$$$ be the position of the second $$$0$$$:

• $$$x$$$ can be the center of the optimal palindrome.
• $$$y$$$ can be the center of the optimal palindrome.
• $$$x$$$ and $$$y$$$ can be on opposite corresponding sides of the palindrome. For instance, $$$[\dots, 0, \dots, j, k, j, \dots, 0, \dots]$$$ for odd palindromes, $$$[\dots, 0, \dots, j, k, k, j, \dots, 0, \dots]$$$ for even palindromes.

We can try each of these choices, and expand from the candidate center as long as the subarray is still palindromic, while keeping track of $$$\operatorname{mex}$$$. The answer is the maximum $$$\operatorname{mex}$$$ among all $$$3$$$ candidates.

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

int n;
vector<int> v;

int solve(int l, int r) {
    set<int> s;
    for(int i = 0; i <= n; i++) s.insert(i);

    while(l >= 0 && r < 2 * n && v[l] == v[r]) {
        s.erase(v[l]);
        l--, r++;
    }

    return *s.begin();
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        v = vector<int> (2 * n);
        for(auto &it : v) cin >> it;

        int x = -1, y;
        for(int i = 0; i < 2 * n; i++) {
            if(!v[i]) {
                if(~x) y = i;
                else x = i;
            }
        }

        cout << max({solve(x, x), solve(y, y), solve((x + y) / 2, (x + y + 1) / 2)}) << endl;
    }
}

Instead of only expanding from the $$$3$$$ possible candidates, we can brute force over all centers (even and odd palindrome centers) and only expand as long as the subarray will stay palindromic. Can you prove why this fits the time limit?

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Look at one height at a time. A cube stays only if every column to its right is tall enough for that height.

The number of cubes that stay in column $$$i$$$ is exactly the suffix minimum $$$s_i$$$.

Let $$$s_i = \min(a_i, a_{i+1}, \dots, a_n)$$$ be the suffix minimum of the array.

The key observation is that a cube at position $$$(i, h)$$$ stays in the same column after the gravity shift if every column to its right also has a cube on height $$$h$$$. In other words, the row $$$h$$$ is already a suffix of occupied cells. This happens exactly when $$$h = s_i$$$.

So, column $$$i$$$ contributes exactly $$$s_i$$$ cubes that do not move, and therefore it contributes $$$a_i - s_i$$$ cubes that do move. Without any operation, the total number of moving cubes is $$$\sum_{i=1}^{n} (a_i - s_i)$$$. Now we try the operation. If $$$a_i \gt s_i$$$, then this decrease does not change any suffix minimum at all, because there is already a smaller somewhere to the right. Such a choice is useless. The only useful positions are those where $$$a_i = s_i$$$, which are exactly the positions where the suffix minimum array changes (i.e., $$$s_i \neq s_{i+1}$$$).

Since suffix minima are non-decreasing from left to right, equal values form contiguous blocks. If we decrease the rightmost element of such a block, then the suffix minimum on the whole block drops by $$$1$$$. This means the number of cubes that stay in place decreases by the length of that block, while the total number of cubes decreases by only $$$1$$$. Consequently, the number of moving cubes increases by $$$\text{block length} - 1$$$.

Therefore, the best strategy is to pick the longest block of equal values in the suffix minimum array. The final formula for the maximum number of moving cubes is:

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<ll> v(n);
        ll sum = 0;
        for(auto &it : v) {
            cin >> it;
            sum += it;
        }

        vector<ll> suf_mn(n);
        suf_mn[n - 1] = v[n - 1];
        sum -= suf_mn[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            suf_mn[i] = min(suf_mn[i + 1], v[i]);
            sum -= suf_mn[i];
        }

        ll mx = -1, cur = 1;
        for(int i = 1; i < n; i++) {
            if(suf_mn[i] == suf_mn[i - 1]) cur++;
            else {
                mx = max(mx, cur);
                cur = 1;
            }
        }

        mx = max(mx, cur);
        cout << sum + mx - 1 << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Cubes on the same height never interact with other heights.

For a fixed height $$$h$$$, the cubes end up in the rightmost $$$\texttt{cnt}[h]$$$ columns, where $$$\texttt{cnt}[h]$$$ is the number of cubes at height $$$h$$$.

After decreasing one column by $$$1$$$, only one height level changes, so the gain value is easy to calculate locally.

Fix some height $$$h$$$. A cube at height $$$h$$$ exists in column $$$i$$$ exactly when $$$a_i \ge h$$$. When gravity shifts to the right, all cubes on the same height behave independently from the other heights, they just slide as far right as possible without overlapping. Therefore, on height $$$h$$$, all cubes occupy the rightmost $$$\texttt{cnt}[h]$$$ columns, where $$$\texttt{cnt}[h]$$$ is the number of columns with $$$a_i \ge h$$$. So the whole problem can be reduced to counting, for each height, how many cubes start there and where they end up.

Let

Then the sum of final column indices of the cubes on height $$$h$$$ is simply the sum of an arithmetic progression:

The sum of initial column indices of the cubes on height $$$h$$$ is the sum of all indices $$$i$$$ such that $$$a_i \ge h$$$. If we sum this over all heights, we get the total movement distance of all cubes. An easy way to compute the initial sum is column-wise instead of height-wise. A cube in column $$$i$$$ contributes $$$i$$$ to the initial column-sum for every height from $$$1$$$ to $$$a_i$$$. So the total initial sum is $$$\sum_{i=1}^n i \cdot a_i$$$. For the final sum, we use the $$$\texttt{cnt}[h]$$$ values above. So if no operation is performed, the answer is $$$\text{final} - \text{initial}$$$.

Now consider the allowed operation. Suppose $$$a_i = x$$$, then the initial sum decreases by exactly $$$i$$$, because one cube from column $$$i$$$ disappears. What happens to the final sum? Only height $$$x$$$ changes, because the column still contributes to all heights $$$1, 2, \dots, x-1$$$, but no longer contributes to height $$$x$$$. So $$$\texttt{cnt}[x]$$$ decreases by $$$1$$$, and all other heights stay unchanged.

For height $$$x$$$, the final sum of occupied columns changes from the rightmost $$$\texttt{cnt}[x]$$$ columns to the rightmost $$$\texttt{cnt}[x]-1$$$ columns. The difference is exactly $$$n - \texttt{cnt}[x] + 1$$$. So the total gain from decreasing $$$a_i$$$ is:

That means we should compute this value for every index $$$i$$$ and take the maximum.

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

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v(n + 1), cnt(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> v[i];
            cnt[v[i]]++;
        }

        vector<int> have(n + 1);
        have[n] = cnt[n];
        for(int i = n - 1; i >= 1; i--) have[i] = have[i + 1] + cnt[i];

        int init = 0, aft = 0;
        for(int i = 1; i <= n; i++) {
            init += i * v[i];
            aft += have[i] * (2 * n - have[i] + 1) / 2;
        }

        int cur = aft - init, mx = 0;
        for(int i = 1; i <= n; i++) mx = max(mx, i - n + have[v[i]] - 1);

        cout << cur + mx << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The length of the array decreases by $$$2$$$ after each operation, so only odd-length subarrays are possibly good.

Think about alternating sum. What can you notice about it after applying some operations?

Alternating sum is invariant. A good subarray must be a positive single element at the end, so the alternating sum must be positive. Is this a sufficient condition?

Let's define:

which is the alternating sum of an array $$$c$$$.

First, every operation keeps the parity of the length unchanged, because the length only decreases by $$$2$$$. Therefore, if an array can be reduced to length $$$1$$$, then its length must be odd.

Now, let's look at the operation. Suppose we choose an index $$$i$$$ and perform the replacement:

In the alternating sum $$$S(c)$$$, the signs of these three positions are either $$$(+, -, +)$$$ or $$$(-, +, -)$$$, depending on the parity of $$$i-1$$$. Their contribution to the total sum is:

This is exactly the contribution of the new element $$$x$$$ at that position. Therefore, the alternating sum is invariant under the operation.

Since the final array has length $$$1$$$, its alternating sum is just that single remaining number, which is positive. Therefore, every good array must have positive alternating sum. So far we have proved a necessary condition: a good array must have odd length and positive alternating sum.

It turns out, the condition is actually sufficient.

Now the problem is reduced to counting subarrays with odd-length and positive alternating sum. Let:

For a subarray $$$[l, r]$$$, if $$$r − l + 1$$$ is odd, then $$$l$$$ and $$$r$$$ have the same parity, and the subarray is good exactly when the corresponding prefix values satisfy:

• If $$$l$$$ is odd, the subarray sum is $$$\texttt{pref}[r] - \texttt{pref}[l-1]$$$. We need $$$\texttt{pref}[r] \gt \texttt{pref}[l-1]$$$.
• If $$$l$$$ is even, the subarray sum is $$$\texttt{pref}[l-1] - \texttt{pref}[r]$$$. We need $$$\texttt{pref}[r] \lt \texttt{pref}[l-1]$$$.

So while scanning $$$r$$$ from left to right, we only need to count previous prefix indices of the opposite type with a smaller or larger prefix value. This is a standard task, which can be done using Fenwick Tree and coordinate compression, or using an ordered set with order statistics.

// written by omsincoconut

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pair<ll, int>, null_type,less<pair<ll, int>>, rb_tree_tag,tree_order_statistics_node_update>

const bool HAVE_CASE = true;

void test_case_run() {
    ll n;
    cin >> n;

    ll a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    ll qc[n+1];
    qc[0] = 0;
    ordered_set oset[2];
    oset[0].insert({0LL, 0});

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        qc[i] = a[i] - qc[i-1];

        ans += oset[(i+1)%2].order_of_key({qc[i], -1});
        oset[i%2].insert({-qc[i], i});
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    if (HAVE_CASE) cin >> t;
    while (t--) test_case_run();
 
    return 0;
}

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

struct FenwickTree {
    int n;
    vector<int> bit;
    FenwickTree(int n) : n(n + 1), bit(n + 1) {}
    int query(int r) {
        int ret = 0;
        while(r > 0) {
            ret += bit[r];
            r -= (r & -r);    
        }

        return ret;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    void update(int idx, int delta) {
        while(idx < n) {
            bit[idx] += delta;
            idx += (idx & -idx);
        }
    }
};

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v(n);
        for(auto &it : v) cin >> it;

        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i++) {
            if(i & 1) pre[i] = pre[i - 1] + v[i - 1];
            else pre[i] = pre[i - 1] - v[i - 1];
        }

        vector<int> h = pre;
        sort(h.begin(), h.end());
        h.erase(unique(h.begin(), h.end()), h.end());
        auto get = [&](int x) { return lower_bound(h.begin(), h.end(), x) - h.begin() + 1; };

        FenwickTree fen_ev(h.size()), fen_od(h.size());
        int ans = 0;

        fen_ev.update(get(0), 1);

        for(int i = 1; i <= n; i++) {
            int x = get(pre[i]);
            if(i & 1) {
                ans += fen_ev.query(x - 1);
                fen_od.update(x, 1);
            }
            else {
                ans += fen_od.query(x + 1, h.size());
                fen_ev.update(x, 1);
            }
        }

        cout << ans << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

For a fixed edge, when does it contribute $$$1$$$ to the answer?

Root the tree anywhere. Let $$$\texttt{cnt}[u]$$$ be the number of leaves in the subtree of $$$u$$$, and $$$u \neq \texttt{root}$$$. The edge $$$\texttt{parent}_u \to u$$$ is used if $$$\texttt{cnt}[u]$$$ is odd.

There can be an unchosen leaf. How to choose which leaf to ignore?

Let's pick any vertex as the root. For every edge connecting a parent to a child $$$u$$$, let $$$\texttt{cnt}[u]$$$ be the total number of leaves in the subtree rooted at $$$u$$$.

Consider this edge alone:

• If $$$\texttt{cnt}[u]$$$ is even, all leaves inside this subtree can be paired with each other internally. This edge does not need to be crossed by any path.
• If $$$\texttt{cnt}[u]$$$ is odd, after pairing as many leaves as possible within the subtree, exactly one leaf will be left over. This leaf must cross the edge to find a pair outside the subtree. Therefore, this edge must be used exactly once.

If the total leaf count is even, every leaf must be paired. An edge is used if and only if its child's subtree contains an odd number of leaves. Hence:

But what if the total leaf count was odd? Exactly one leaf will remain unchosen. Leaving a leaf $$$x$$$ unchosen allows us to save or lose the cost of some edges. Specifically, for every edge on the path from the root to $$$x$$$, the parity of the number of leaves in the corresponding child subtree changes:

• If the subtree had an odd number of leaves, it becomes even, so that edge is no longer needed;
• If the subtree had an even number of leaves, it becomes odd, so that edge becomes needed.

Therefore, if the total number of leaves is odd, we want to choose a leaf $$$x$$$ such that the value

is maximized.

Let's define $$$\texttt{mx}[u]$$$ as:

Thus, the answer for the odd leaves case is:

We can compute $$$\texttt{cnt}[u]$$$ for every vertex using a DFS. Then, in the same DFS or in a separate one, we compute $$$\texttt{mx}[u]$$$. The transition is:

and for a leaf, $$$\texttt{mx}[u] = 0$$$.

Therefore,

• If $$$\texttt{cnt}[\texttt{root}]$$$ is even, the answer is just the number of edges whose child subtree has odd $$$\texttt{cnt}[u]$$$;
• If $$$\texttt{cnt}[\texttt{root}]$$$ is odd, subtract $$$\texttt{mx}[\texttt{root}]$$$ from that answer.

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

const int N = 2e5 + 10;

int n;
vector<int> adj[N];
int mx[N], cnt[N];

void dfs(int u, int par) {
    cnt[u] = (adj[u].size() == 1);

    for(int v : adj[u]) {
        if(v == par) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
    
    int cur = 0;
    for(int v : adj[u]) {
        if(v == par) continue;
        int w = (cnt[v] & 1) ? 1 : -1;
        cur = max(cur, mx[v] + w);
    }

    mx[u] = cur;
}

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

    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) adj[i].clear();

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

        dfs(1, 0);

        int ans = 0;
        for(int u = 2; u <= n; u++) {
            if(cnt[u] & 1) ans++;
        }

        if(!(cnt[1] & 1)) cout << ans << endl;
        else cout << ans - mx[1] << endl;
    }

    return 0;
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

When is the optimal time to use the button?

It's not necessary to use the button when a door is already open. Therefore, it's always optimal to use the button as soon as we hit a closed door.

Let's call the position of the first closed door $$$l$$$ and the position of the last closed door $$$r$$$. The length of this interval is $$$r - l + 1$$$, so we need to check that $$$x$$$ is greater than or equal to $$$r - l + 1$$$.

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

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

    int l = 1e5, r = -1;
    for(int i = 0; i < n; i++) {
        int door;
        cin >> door;

        if(door == 1) {
            l = min(l, i);
            r = max(r, i);
        }
    }

    cout << (x >= r - l + 1 ? "YES" : "NO") << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

When are we unable to remove the maximum element?

We can always remove the maximum element as long as it exists between two elements. How can we generalize this?

In a permutation, the maximum element can only occur once. Since all other elements are guaranteed to be smaller than maximum, we can remove the maximum if there exists an element on its left and another on its right.

After we remove the maximum element, another maximum appears, which we also want to remove. This process can keep going until the length of the permutation becomes $$$2$$$, since both remaining elements are on the ends and can not be removed.

Therefore, any permutation with $$$1$$$ and $$$2$$$ on the ends is acceptable, since any value greater than $$$2$$$ will eventually be a maximum in between two elements.

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

void solve() {
    int n;
    cin >> n;
    
    for(int i = 2; i <= n; i++) cout << i << ' ';
    cout << 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

The last segment of a valid partition must contain all distinct elements of the array.

From the first hint, we can say that any segment ending at some position $$$r$$$ must contain all distinct elements of the prefix $$$[1, r]$$$.

Claim: In a valid partition, if a segment ends at some position $$$r$$$, it must contain all distinct elements in the prefix $$$[1, r]$$$.

Let $$$d_i$$$ be the number of distinct elements in the range $$$[1, i]$$$. To maximize the number of segments, we make them as small as possible. Let $$$r$$$ be the end position for the current segment, we will iterate from $$$r$$$ to the left until we find the first position $$$l$$$ such that the number of distinct elements in $$$[l, r] = d_r$$$, then increment our answer and set $$$r = l - 1$$$. We repeat until $$$l=1$$$.

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

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> distinct(n), freq(n + 1);
    
    int total = 0;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        freq[v[i]]++;
        if(freq[v[i]] == 1) distinct[i] = 1;
        distinct[i] += (i ? distinct[i - 1] : 0);
    }

    fill(freq.begin(), freq.end(), 0);

    int ans = 0, end = n - 1;
    total = 0;
    for(int i = n - 1; i >= 0; i--) {
        freq[v[i]]++;
        if(freq[v[i]] == 1) total++;
        
        if(total == distinct[end]) {
            ans++;
            for(int j = i; j <= end; j++) freq[v[j]] = 0;
            end = i - 1;
            total = 0;
        }
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

Similarly to the above solution, we can have a segment $$$[l, r]$$$ if and only if $$$[l, r]$$$ contains all of the same elements as $$$[1, r]$$$. We now build our segments greedily from the front, iterating through each element. Suppose the element we are currently on is $$$a_i$$$. We make the following claim: if we can end the current segment at $$$a_i$$$, we should do so. (There is one exception to this, which is covered after the proof.)

Now, we just end segments whenever we can. The only "special" case that needs to be taken care of, is whether or not the last segment is legal. But if it isn't, we can simply merge it into the last legal segment, which only makes this segment bigger and thus doesn't cause any issues since it has at least as many distinct values as before. It turns out that this doesn't really affect the implementation, since we just have to count the number of times we can end the segment.

So how do we do this quickly? Let's keep a set of all elements in $$$[1, i]$$$, and a set of all elements in $$$[l, i]$$$. Then if these sets are the same size, we know that $$$[l, i]$$$ contains all of the same elements as $$$[1, i]$$$. If this is the case, we will end the segment at $$$i$$$. Then we will increment our answer, and set $$$l:=i+1$$$ (in the implementation, we will clear the set of elements in $$$[l, i]$$$).

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, ans = 0;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    set<int> cur, seen;
    for(int i=0; i<n; i++){
        cur.insert(a[i]);
        seen.insert(a[i]);
        if(cur.size() == seen.size()){
            ans++;
            seen.clear();
        }
    }
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

What happens when we do $$$1$$$ operation of the first type and $$$1$$$ operation of the second type?

If we perform both types of the operation once, each element $$$a_i$$$ is decreased by $$$n + 1$$$. Suppose we are able to explode the array with $$$x$$$ operations of the first type and $$$y$$$ operations of the second type. Then, let's pair as many operations as we can, allowing us to perform $$$\min(x, y)$$$ pairs of operations.

Now, assume we finished pairing the operations. This leaves us with some operations (possibly none) of only one type, so the array must become an arithmetic sequence; the absolute difference between two consecutive elements is the number of operations that we have to perform.

We don't yet know the number of pairs of operations $$$\min(x, y)$$$ that we have to perform, since we don't know the value of $$$x$$$ and $$$y$$$, but we now know the number of extra operations we perform after pairing the operations. Since we need to have an arithmetic sequence in order to explode the array, we should verify that the difference between adjacent elements are all the same. Let's call the number of extra operations $$$k = |x-y|$$$, which is equal to the difference between adjacent elements. If the array is increasing, the extra operations must be of the first type. Otherwise, they must be of the second type.

Now, let's first perform the $$$k$$$ operations on the array. Since the consecutive differences are all the same, after performing the $$$k$$$ extra operations, all elements should be equal. It remains to check that the elements are non-negative and are divisible by $$$n + 1$$$, so we can now perform pairs of operations to explode the array.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for(auto &it : v) cin >> it;

    long long diff = v[1] - v[0];
    bool bad = 0;
    for(int i = 2; i < n; i++) if(diff != v[i] - v[i - 1]) bad = 1;
    
    if(bad) {
        cout << "NO" << endl;
        return;
    }
    
    for(int i = 0; i < n; i++)
        v[i] = v[i] + (diff < 0 ? diff * (n - i) : -diff * (i + 1));
        
    cout << (v[0] >= 0 && v[0] % (n + 1) == 0 ? "YES" : "NO") << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

Suppose we did $$$x$$$ operations of the first type and $$$y$$$ operations of the second type to explode the array. What must the value of $$$a_1$$$ be?

From the first hint, we know the first element $$$a_1 = 1 \cdot x + n \cdot y$$$. What about the second element?

Let's consider the first two elements. Suppose we needed $$$x$$$ operations of the first type and $$$y$$$ operations of the second type to explode the array, then we know $$$a_1 = 1 \cdot x + n \cdot y$$$. For the second element, we know $$$a_2 = 2 \cdot x + (n - 1) \cdot y$$$.

Now, let's solve for $$$x$$$ and $$$y$$$. Subtracting $$$a_2$$$ from $$$a_1$$$ gives us

\begin{align*} a_1 — a_2 &= (x + n \cdot y) — (2 \cdot x + (n — 1) \cdot y) \newline &= y — x \newline \Longrightarrow x &= y — a_1 + a_2 \end{align*}

Let's substitute $$$y - a_1 + a_2$$$ for $$$x$$$ in the first formula.

\begin{align*} a_1 &= (y — a_1 + a_2) + n \cdot y \newline \Longrightarrow y &= \frac{2 \cdot a_1 — a_2}{n + 1} \end{align*}

Now, we have the value of $$$y$$$, which means we can easily find the value of $$$x$$$. From the formula $$$x = y - a_1 + a_2$$$, substitute $$$y$$$ with its value to get $$$x$$$. What remains is just to check if the array becomes $$$a_1 = a_2 = \dots = a_n = 0$$$ after all the operations.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    ll n;
    cin >> n;
    vector<ll> v(n);
    for(auto &it : v) cin >> it;

    ll y = (2 * v[0] - v[1]) / (n + 1);
    ll x = v[1] - v[0] + y;

    if(y < 0 || x < 0) {
        cout << "NO" << endl;
        return;
    }

    for(int i = 0; i < n; i++) {
        v[i] -= x * (i + 1);
        v[i] -= y * (n - i);
    }

    for(int i = 0; i < n; i++) {
        if(v[i] != 0) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

If we can get a match at position $$$i$$$, then we can have at least $$$i$$$ matches. Why is this true?

For a certain position $$$i$$$, given the ability to remove index $$$i + 1$$$, we can pull any value from the range $$$[i + 2, n]$$$.

It's clear to see that if a match exists at position $$$i$$$, then we can repeatedly set $$$a_j := b_{j+1}$$$ and $$$b_j := a_{j+1}$$$ for all $$$j$$$, where $$$j$$$ starts as $$$i - 1$$$ and goes backwards until the start of the array. This allows us to have at least $$$i$$$ matches (including the match at position $$$i$$$).

Therefore, the optimal approach is to maximize the index $$$i$$$ where $$$a_i = b_i$$$. Suppose we can't remove any element. Then, for some $$$a_i$$$, we can set it to any $$$b_j$$$ such that $$$j \pmod 2 \neq i \pmod 2$$$ and $$$j \gt i$$$, or set it to any $$$a_j$$$ such that $$$j \pmod 2 = i \pmod 2$$$ and $$$j \gt i$$$.

However, if we wanted to set $$$a_i$$$ to some $$$b_j$$$ where $$$j \pmod 2 = i \pmod 2$$$, then we can just remove index $$$i + 1$$$ from the array. By similar reasoning, we can set $$$a_i$$$ to any $$$a_j$$$ where $$$j \pmod 2 \neq i \pmod 2$$$ and $$$j \gt i+1$$$. Notice that we removed index $$$i + 1$$$, so we can't set $$$a_i := a_{i+1}$$$. Now, we know that we can set any $$$a_i$$$ to any $$$a_j$$$ or $$$b_j$$$ such that $$$j \gt i + 1$$$. This can be generalized for $$$b_i$$$ as well.

So the solution is that, for each position $$$i$$$, we want to check if any $$$a_j$$$ or $$$b_j$$$, such that $$$j \gt i + 1$$$, matches $$$a_i$$$ or $$$b_i$$$, allowing us to get a match at position $$$i$$$. We also need to check if position $$$i$$$ already contains a match, or if $$$a_i = a_{i + 1}$$$ or $$$b_i = b_{i + 1}$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);

    for(auto &it : a) cin >> it;
    for(auto &it : b) cin >> it;

    vector<bool> seen(n + 1);
    if(a.back() == b.back()) {
        cout << n << endl;
        return;
    }

    int ans = -1;
    for(int i = n - 2; i >= 0; i--) {
        if(a[i] == b[i] || a[i] == a[i + 1] || b[i] == b[i + 1] || seen[a[i]] || seen[b[i]]) {
            ans = i;
            break;
        }

        seen[a[i + 1]] = seen[b[i + 1]] = true;
    }

    cout << ans + 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

There can only be at most $$$2$$$ leaves. This means the tree can either be a chain or Y-shaped.

If the tree is a chain, subtree sums will always be strictly increasing as you move towards the root, which means that the answer for any chain is $$$2^n$$$.

Claim: For an answer to exist, the tree should have at most $$$2$$$ leaves.

We only need to consider two cases, the case of $$$1$$$ leaf and the case of $$$2$$$ leaves.

• $$$1$$$ leaf case: We can see that $$$\lbrace 1,2 \rbrace$$$ are positive values, so $$$s$$$ is strictly increasing as you move towards the root. Therefore, any array $$$a$$$ will be valid. The answer for this case would be $$$2^n$$$.

• $$$2$$$ leaves case: Let $$$v$$$ be the lowest common ancestor between leaf $$$x$$$ and leaf $$$y$$$. From $$$v$$$ going up towards the root, we can see that it follows the same idea of the $$$1$$$ leaf case, which means that any vertex in the path between the root and $$$v$$$ can be assigned to either $$$1$$$ or $$$2$$$. Without loss of generality, suppose leaf $$$x$$$ has smaller depth than leaf $$$y$$$. Say we assigned $$$a_x = 1$$$ and $$$a_y = 2$$$; it is easy to see that we are forced to assign vertices to $$$2$$$ as we're going up, until we eventually finish assigning a branch. So the number of vertices that are free to be assigned to either $$$1$$$ or $$$2$$$ in $$$y$$$'s branch is simply $$$\texttt{depth}_y - \texttt{depth}_x$$$. If we assign $$$a_x = 2$$$ and $$$a_y = 1$$$ instead, then $$$y$$$ would have one more vertex forced to be assigned to $$$2$$$, meaning there are only $$$\texttt{depth}_y - \texttt{depth}_x - 1$$$ free vertices in $$$y$$$'s branch. Finally, the last case to be checked is if $$$\texttt{depth}_x = \texttt{depth}_y$$$. In this case, whether we assign $$$x$$$ to $$$1$$$ and $$$y$$$ to $$$2$$$, or we assign $$$x$$$ to $$$2$$$ and $$$y$$$ to $$$1$$$, all vertices in both branches are forced, so there are no free vertices in either branch.

Let the number of leaves be $$$\texttt{cnt}$$$. Then we have that: $$$\texttt{Answer}$$$ = \begin{cases} 0 &\text{if }\texttt{cnt} > 2 \newline 2^n &\text{if }\texttt{cnt} = 1 \newline (2^{\texttt{depth}_y — \texttt{depth}_x} + 2^{\texttt{depth}_y — \texttt{depth}_x — 1}) \cdot 2^{\texttt{depth}_v} &\text{if }\texttt{cnt} = 2\text{ and }\texttt{depth}_x < \texttt{depth}_y \newline 2^{\texttt{depth}_v} + 2^{\texttt{depth}_v} &\text{if }\texttt{cnt} = 2\text{ and }\texttt{depth}_x = \texttt{depth}_y \end{cases}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 10, MOD = 1e9 + 7;
#define int long long
 
vector<int> adj[N], lens;
int pw[N];
int lca;
 
void dfs(int u, int par, int len) {
    if(adj[u].size() > 2) lca = len;
    
    bool leaf = true;
    for(int v : adj[u]) {
        if(v != par) {
            dfs(v, u, len + 1);
            leaf = false;
        }
    }
 
    if(leaf) lens.push_back(len);
}

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

    for(int i = 1; i <= n; i++) adj[i].clear();
    lens.clear();
    lca = -1;

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

    adj[1].push_back(0); // dummy node
    dfs(1, 0, 1);
    if(lens.size() > 2) cout << 0 << endl;
    else if(lens.size() == 1) cout << pw[n] << endl;
    else {
        int diff = abs(lens[0] - lens[1]);
        int x = diff + lca;
        if(diff) cout << (pw[x] + pw[x - 1]) % MOD << endl;
        else cout << (2 * pw[x]) % MOD << endl;
    }
}

signed main() {
    pw[0] = 1;
    for(int i = 1; i < N; i++) pw[i] = (pw[i - 1] * 2) % MOD;

    int t;
    cin >> t;
    while(t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

Try fixing the minimum edge on the path.

There are two common ways to solve this problem; one uses DSU and the other uses Dijkstra. I will explain the Dijkstra approach here:

The main idea here is to pick some edge $$$e$$$ and pretend that $$$e$$$ is the minimum-weight edge, then find the smallest maximum edge weight across all paths containing $$$e$$$. This method will only ever overestimate the answer, and equality holds when we choose $$$e$$$ to be the minimum-weight edge of the optimal path, so the answer must be the minimum of these values across all possible choices.

Lets define a new cost function. Instead of $$$cost(w_1,...,w_k) = (\min_{i = 1}^{k}{w_i}) + (\max_{i=1}^{k}{w_i})$$$, let's define $$$cost_j(w_1,...,w_k) = w_j + (\max_{i=1}^{k}{w_i})$$$, i.e. the weight of edge $$$j$$$ + the max weight. By the above reasoning, the minimum value of $$$cost_j(w_1,...,w_k)$$$ across all $$$j$$$ is the same as the minimum value of $$$cost(w_1,...,w_k)$$$.

This function is a lot easier to minimize than the initial one. Let's iterate over each edge $$$j$$$ — denote its endpoints to be $$$u_j$$$ and $$$v_j$$$, and its weight to be $$$w_j$$$ — and find the minimum value of $$$cost_j(w_1,...,w_k)$$$. Now we just need to find the minimum possible value of $$$\max_{i=1}^{k}{w_i}$$$ across all paths that contain $$$j$$$. To do this, we just want to minimize the max weight of the path from $$$1$$$ to $$$u$$$ and from $$$v$$$ to $$$n$$$, so we have reduced the problem to finding the minimum max weight on a path from $$$1$$$ to all other nodes, and finding the minimum max weight on a path from every node to $$$n$$$. But how do we do this?

The idea is very similar to Dijkstra — recall the proof that Dijkstra finds the minimum sum of weights on a path. The main idea is that whenever we pop a node from the heap, we know that the minimum cost to it has already been found. We can use the same reasoning to prove that if we change path cost from path sum to path max, then the algorithm will still work. So all we have to do is simply run this max Dijkstra variation from $$$1$$$ and from $$$n$$$.

Now we just need to find the minimum value of $$$w_i + \max(\mathrm{cost}(1, u_i), \mathrm{cost}(v_i, n), w_i)$$$ across all edges $$$i$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;

        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    auto uwu = [&](int u) -> vector<ll>{
        vector<ll> dis(n, 1e18);
        vector<bool> vis(n);       

        priority_queue<array<ll, 2>> q;
        q.push({0, u});
        while (q.size()){
            auto [d, c] = q.top();
            d = -d;
            q.pop();

            if (vis[c])
                continue;
            vis[c] = true;
            dis[c] = d;

            for (auto [x, w] : g[c]){
                if (vis[x])
                    continue;

                q.push({-max(d, 1LL * w), x});
            }
        }

        return dis;
    };

    ll ans = 1e18;
    vector<ll> dis_s = uwu(0), dis_t = uwu(n - 1);
    for (int u = 0; u < n; u++){
        for (auto [v, w] : g[u]){
            ans = min(ans, {max({dis_s[u], dis_t[v], 1LL * w}) + w});
        }
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴

Try to think of an offline solution.

Rephrase the problem to maximum subarray sums.

The unusual memory limit is meant to cut persistent segment tree solutions. Obviously it isn't perfect (I apologize if it caused issues), but it's the best I could do.

Let's first pretend that $$$x$$$ in the problem is fixed. For example, if $$$x = 2$$$, then we want to find the maximum $$$k$$$ such that $$$2$$$ is a $$$k$$$-majority of some subarray. To solve this problem, let's build an array $$$b_1, b_2, \ldots, b_n$$$ such that $$$b_i = 1$$$ if $$$a_i = x$$$, and $$$b_i = -1$$$ otherwise. Let $$$s$$$ be the maximum subarray sum over all subarrays of $$$b$$$. The answer to the problem is $$$\lfloor \frac{s}{2} \rfloor$$$.

Now let's consider how to handle updates. If we are asked to update index $$$k$$$ with an element $$$y$$$, we have two cases. If $$$a_k \neq x$$$ and $$$y=x$$$, then we update $$$b_k = 1$$$. Otherwise, if $$$a_k = x$$$ and $$$y \neq x$$$, then we set $$$b_k = -1$$$. Then, we can answer the query by finding the maximum subarray sum of $$$b$$$ using a segment tree. This is a standard problem.

Let $$$b_i$$$ denote the sequence of arrays that correspond to the array $$$b$$$ that fixes $$$i$$$. Now let's stop fixing $$$x$$$. For each update, notice that at most two of the arrays in the sequence is modified (precisely, $$$b_{a_k}$$$ and $$$b_y$$$). To answer the query, let $$$\texttt{res}_x$$$ denote the answer maximum subarray sums of arrays $$$b_x$$$ for all $$$x \in [1, n]$$$ so far. The answer to this query is just $$$\lfloor \frac{\max(\texttt{res}_1, \texttt{res}_2, \ldots, \texttt{res}_n)}{2} \rfloor$$$. Additionally, because of the update, notice that only $$$\texttt{res}_{a_k}$$$ and $$$\texttt{res}_y$$$ might change. This motivates an approach where we track $$$\texttt{res}_x$$$ overall all $$$x$$$ and extract the maximum.

For each $$$x$$$, let's keep track of all updates that modifies an index $$$k$$$ where it was $$$a_k = x$$$ originally or $$$a_k = x$$$ after the update. Let Notice that for the former case, we are setting $$$b_{x_k} = -1$$$ and in the latter case, we are setting $$$b_{x_k} = -1$$$. Notice that we are tracking at most $$$2q$$$ updates because each update modifies at most two $$$b_x$$$, as explained in the previous paragraph. Let's store all such updates in an array $$$v_x$$$.

Let's try to construct $$$b_x$$$ for each $$$x \in [1, n]$$$ now. To do so, let's first create a global array $$$b$$$, where initially $$$b_i = -1$$$ over all $$$1 \leq i \leq n$$$. Then, we can iterate over all elements of $$$a$$$ where $$$a_j = x$$$ and set $$$b_j = 1$$$. Now we can iterate over the queries in $$$v_x$$$. For each query in $$$v_x$$$, we can track the maximum subarray sum of $$$b$$$ after each update. If this is the $$$j$$$'th query, then we must note that after the $$$j$$$'th query, we will update $$$\texttt{res}_x$$$. We can iterate over all $$$x \in [1, n]$$$ and perform the above process in $$$O((n + q)\log n))$$$ time total.

Now, we know when to update $$$\texttt{res}_x$$$ for each $$$x \in [1, n]$$$. Finally, let's loop through all $$$q$$$ queries one last time and store all $$$\texttt{res}_x$$$ in a multiset. If the $$$j$$$'th query affects $$$\texttt{res}_y$$$, then we will erase the old $$$\texttt{res}_y$$$ from the multiset and replace it with the new one. To answer the query, we can simply extract the maximum element in the multiset.

First, consider the $$$k$$$-majority for a single element $$$y$$$. By definition, for a subarray $$$b$$$, the $$$k$$$-majority is given by $$$\lfloor{\frac{2 \cdot \text{cnt}(y) - |b|}{2}}\rfloor$$$. Instead of computing this directly, we construct a new array $$$c$$$, where $$$c_i = 1$$$ if $$$b_i = y$$$ and $$$c_i = -1$$$ otherwise. Then, the $$$k$$$-majority for the element $$$y$$$ is equivalent to the maximum sum among all subarrays of $$$c$$$, floor-divided by 2. This transformation reduces our problem to finding the maximal subarray sum.

Since we must efficiently handle updates, we require a dynamic data structure capable of both updates and queries. This can be accomplished using a segment tree that maintains the maximum subarray sum, maximum prefix sum, maximum suffix sum, and total sum within each node.

To apply this method to all possible values of $$$y$$$, we process all queries offline. Initially, we set all elements of array $$$c$$$ to $$$-1$$$. For each distinct element $$$y$$$, we first update the array $$$c$$$ by setting $$$c_i = 1$$$ wherever $$$a_i$$$ initially equals $$$y$$$. Next, we sequentially apply all updates involving $$$y$$$, calculating the maximal $$$k$$$-majority for $$$y$$$ after each update. This procedure generates $$$q + n$$$ segments, each segment holding the maximal $$$k$$$-majority information for an element $$$y$$$. By inserting and removing these maximum values into a multiset, we efficiently retrieve the global maximal $$$k$$$-majority at every step. Giving $$$O((n + q)\log n)$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};

struct Node {
    int sum;    // total sum of segment
    int pref;   // max prefix sum
    int suff;   // max suffix sum
    int best;   // max subarray sum
    Node(): sum(0), pref(0), suff(0), best(0) {}
    Node(int x): sum(x), pref(max(0,x)), suff(max(0,x)), best(max(0,x)) {}
};

Node merge(const Node &L, const Node &R) {
    Node res;
    res.sum  = L.sum + R.sum;
    res.pref = max(L.pref, L.sum + R.pref);
    res.suff = max(R.suff, R.sum + L.suff);
    res.best = max({ L.best, R.best, L.suff + R.pref });
    return res;
}

struct segtree {
    int n;
    vector<Node> st;
     segtree(int _n) {
        n = _n;
        st.resize(4*n);
        build(1, 0, n-1);
    }
    void build(int p, int l, int r) {
        if (l == r) {
            st[p] = Node(-1);
            return;
        }
        int m = (l + r) / 2;
        build(p<<1,   l,   m);
        build(p<<1|1, m+1, r);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    void update(int p, int l, int r, int idx, int val) {
        if (l == r) {
            st[p] = Node(val);
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) update(p<<1,   l,   m, idx, val);
        else          update(p<<1|1, m+1, r, idx, val);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    void update(int idx, int val) {
        update(1, 0, n-1, idx, val);
    }
    Node query(int p, int l, int r, int i, int j) {
        if (i > r || j < l) {
            Node nullnode;
            nullnode.sum = 0;
            nullnode.pref = nullnode.suff = nullnode.best = INT_MIN;
            return nullnode;
        }
        if (l >= i && r <= j) {
            return st[p];
        }
        int m = (l + r) / 2;
        Node L = query(p<<1,   l,   m, i, j);
        Node R = query(p<<1|1, m+1, r, i, j);
        if (L.best == INT_MIN) return R;
        if (R.best == INT_MIN) return L;
        return merge(L, R);
    }
    int max_subarray() {
        Node res = query(1, 0, n-1, 0, n-1);
        return res.best;
    }
};

void solve() {
	int n, q; cin >> n >> q;
	vector<int> a(n); cin >> a;
	vector<vector<int>> at(n+1);
	FOR(i,0,n) at[a[i]].pb(i);
	vector<vector<array<int, 3>>> updates(n+1);
	FOR(idx,0,q){
		int i, x; cin >> i >> x;
		--i;
		if(x != a[i]){
			updates[a[i]].pb({idx, i, -1});
			a[i] = x;
			updates[x].pb({idx, i, 1});
		}
	}
	vector<vector<int>> final_at(n+1);
	FOR(i,0,n) final_at[a[i]].pb(i);
	segtree st(n);
	vector<int> init(n+1);
	vector<vector<pair<int,int>>> change(q);
	FOR(x,1,n+1){
		trav(i, at[x]){
			st.update(i, 1);
		}
		int cur = st.max_subarray();
		init[x] = cur;
		trav(i, updates[x]){
			st.update(i[1], i[2]);
			int new_cur = st.max_subarray();
			change[i[0]].pb({cur, new_cur});
			cur = new_cur;
		}
		trav(i, final_at[x]){
			st.update(i, -1);
		}
	}
	multiset<int> ms;
	FOR(i,1,n+1) ms.insert(init[i]);
	FOR(i,0,q){
		trav(j, change[i]){
			ms.erase(ms.find(j.F));
			ms.insert(j.S);
		}
		cout << *prev(ms.end())/2 << " ";
	}
	cout << "\n";
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

• Good problem 😁
• Average problem 🤔
• Bad problem 😭
• Did not solve 😴