Récords al revés#13116

Récords al revés (Editorial)

Solution

Let $p r e f_{k}$ pref_k denote the number of record positions among the first $k$ elements of the original array, and let $t o t a l$ be the total number of record positions in the entire array.

Consider reversing the first $k$ elements.

Notice that the record positions after position $k$ remain unchanged. Indeed, for each such position, the set of preceding elements stays the same, so their maximum does not change.

Therefore, we only need to determine how many record positions there will be among the first $k$ elements after the reversal.

Let this number be $r e v_{k}$ rev_k. Then the answer after reversing the prefix is

c u r_{k} = t o t a l - p r e f_{k} + r e v_{k} .

cur_k = total - pref_k + rev_k.

We can calculate all values of $r e v_{k}$ rev_k using a monotonic stack.

After reversing the first $k$ elements, an element of the original prefix becomes a record if and only if it is strictly greater than every element to its right within that prefix.

We process the array from left to right and maintain a stack of such elements. The values in the stack are kept in strictly decreasing order.

When processing the next element $a_{i}$ a_i, we remove all elements from the top of the stack that are less than or equal to $a_{i}$ a_i, and then push $a_{i}$ a_i.

This is correct because $a_{i}$ a_i is located to the right of all previously processed elements. Therefore, none of the removed elements can become a record after reversing the prefix. The element $a_{i}$ a_i itself always becomes a record, since it will be the first element after the reversal.

Thus, after processing the first $k$ elements, the size of the stack equals $r e v_{k}$ rev_k.

We can also maintain $p r e f_{k}$ pref_k while processing the array: the current element creates a new record position if and only if it is strictly greater than the maximum of all preceding elements.

Therefore, for every $k$ , we can calculate

r e v_{k} - p r e f_{k} .

rev_k - pref_k.

Since we may perform at most one operation, we must also consider leaving the array unchanged.

The final answer is

t o t a l + max (0, 1 \leq k \leq n max (r e v_{k} - p r e f_{k})) .

total + \max\left(0,\max_{1 \le k \le n}(rev_k-pref_k)\right).

Complexity Analysis

Each element is pushed onto the stack exactly once and removed at most once. All other operations take $O (1)$ time per element.

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

Implementation

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

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

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> st;

    int pref = 0, mx = 0, best = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] > mx) {
            mx = a[i];
            pref++;
        }

        while (!st.empty() && st.back() <= a[i]) {
            st.pop_back();
        }

        st.push_back(a[i]);

        best = max(best, (int)st.size() - pref);
    }

    cout << pref + best << '\n';
}

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

    solve();
}