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 😴