平方做法

暴力复杂度瓶颈在排序上，时间复杂度。

为了优化排序操作至，可以多维护一个已排序的序列，执行排序操作时直接赋值即可。可以使用有序集合或者数组，最终复杂度均为。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

vector<int> cur;
multiset<int> st;

void PushBack(int x) {
    cur.push_back(x);
    st.insert(x);
}

void PopBack() {
    st.erase(st.find(cur.back()));
    cur.pop_back();
}

int Get(int idx) {
    return cur[idx];
}

void Insert(int idx, int x) {
    st.insert(x);
    cur.insert(cur.begin() + (idx + 1), x);
}

void Sort() {
    cur.assign(st.begin(), st.end());
}

void SortReverse() {
    cur.assign(st.rbegin(), st.rend());
}

int Size() {
    return cur.size();
}

void Output() {
    for (const auto& x : cur) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int op;
    int x;
    int idx;
    int q;
    cin >> q;
    while (q--) {
        cin >> op;
        switch (op) {
            case 1:
                cin >> x;
                PushBack(x);
                break;
            case 2:
                PopBack();
                break;
            case 3:
                cin >> idx;
                cout << Get(idx) << '\n';
                break;
            case 4:
                cin >> idx >> x;
                Insert(idx, x);
                break;
            case 5:
                Sort();
                break;
            case 6:
                SortReverse();
                break;
            case 7:
                cout << Size() << '\n';
                break;
            default:
                Output();
                break;
        }
    }
    return 0;
}