题解 | #齐齐排序#

不知道为什么其他题解都写的 $O(nm\log n)$ 的暴力。给一篇 $O(n\log n)$ 的做法。

发现只存在前缀操作，显然 $x$ 较大的会覆盖 $x$ 较小的操作。

容易发现有效操作的 $x$ 形成一个后缀最大值序列。对于每一个 $i$ ，找到最后一个覆盖它的操作类型。

先填完没有被操作过的位置（显然这样的位置在序列末），用一个 multiset 装剩下所有数。

倒序遍历还未填的位置，若这个位置上的标记是升序，则填最大值；否则填最小值。

查看代码

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
    const auto stime = std::chrono::steady_clock::now();
#endif
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    std::vector<std::pair<int, int> > q(m + 1);
    for (int i = 1; i <= m; ++i)
        std::cin >> q[i].first >> q[i].second;
    int mx = 0;
    std::vector<int> tag(n + 1);
    for (int i = m; i; --i)
        if (q[i].second > mx) {
            mx = q[i].second;
            tag[q[i].second] = q[i].first;
        }
    std::multiset<int> t;
    for (int i = 1; i <= mx; ++i)
        t.insert(a[i]);
    for (int i = mx, st = 0; i; --i) {
        if (tag[i])
            st = tag[i];
        if (st == 1)
            a[i] = *--t.end(), t.erase(--t.end());
        else
            a[i] = *t.begin(), t.erase(t.begin());
    }
    for (int i = 1; i <= n; ++i)
        std::cout << a[i] << ' ';
    std::cout << '\n';
#ifndef ONLINE_JUDGE
    std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
    return 0;
}