Рекорди навпаки#13116

Рекорди навпаки (Розбір)

Розв'язок

Нехай $p r e f_{k}$ pref_k — кількість рекордних позицій серед перших $k$ елементів початкового масиву, а $t o t a l$ — кількість рекордних позицій у всьому масиві.

Розглянемо операцію розвороту перших $k$ елементів.

Зауважимо, що рекордність позицій після $k$ не зміниться. Справді, для кожної такої позиції набір попередніх елементів залишається тим самим, а отже, не змінюється і їхній максимум.

Таким чином, достатньо визначити, скільки рекордних позицій буде серед перших $k$ елементів після розвороту.

Позначимо цю кількість через $r e v_{k}$ rev_k. Тоді відповідь після розвороту дорівнюватиме

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.

Знайдемо всі значення $r e v_{k}$ rev_k за допомогою монотонного стека.

Після розвороту перших $k$ елементів рекордними будуть саме ті елементи початкового префікса, які строго більші за всі елементи праворуч від них у цьому префіксі.

Будемо перебирати елементи масиву зліва направо та підтримувати стек таких елементів. Значення у стеку зберігатимемо у строго спадному порядку.

При додаванні чергового елемента $a_{i}$ a_i видалимо з кінця стека всі значення, які не перевищують $a_{i}$ a_i, після чого додамо $a_{i}$ a_i.

Це коректно, оскільки $a_{i}$ a_i стоїть правіше за всі попередні елементи, тому жоден із видалених елементів більше не може бути рекордним після розвороту префікса. Сам $a_{i}$ a_i завжди буде рекордним, оскільки після розвороту він стане першим.

Отже, після обробки перших $k$ елементів розмір стека дорівнюватиме $r e v_{k}$ rev_k.

Кількість $p r e f_{k}$ pref_k також легко підтримувати під час проходу масивом: черговий елемент утворює нову рекордну позицію тоді й лише тоді, коли він строго більший за максимум усіх попередніх елементів.

Тому для кожного $k$ можемо знайти значення

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

rev_k - pref_k.

Оскільки дозволено виконати не більш ніж одну операцію, також врахуємо можливість нічого не змінювати.

Остаточна відповідь:

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

Асимптотична складність

Кожен елемент додається до стека рівно один раз і видаляється з нього не більш ніж один раз. Усі інші операції виконуються за $O (1)$ для кожного елемента.

Отже, часова складність становить $O (n)$ , а просторова — $O (n)$ .

Реалізація

#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();
}