C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

60分：

思路：

$通过sort函数每次对给定区间操作一下即可$

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

const int N = 1e5 + 10;

int n, m;
int a[N];

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) a[i] = i;

    while (m --) {
        int p, q; cin >> p >> q;
        if (p) 
            sort(a + q, a + n + 1);
        else 
            sort(a + 1, a + q + 1, cmp);
    }

    for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
    return 0;
}

100分：

思路：

思维 栈

$解析看代码$

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

#define x first
#define y second

const int N = 1e5 + 10;
typedef pair<int, int> pii;

int n, m;
pii stk[N];
int ans[N];

int main() {
    cin >> n >> m;
    int top = 0; // 定义栈顶
    while (m --) {
        int p, q; cin >> p >> q;
        if (!p) { // p == 0, 前缀操作
            while (top && stk[top].x == 0) q = max(q, stk[top --].y); // 两个连续的前缀操作，保留较大的
            while (top >= 2 && stk[top - 1].y <= q) top -= 2; // 删掉前面所有比当前长度小的操作
            stk[ ++ top] = {0, q}; // 把当前的前缀操作加入栈里
        }
        else if (top) { // 后缀操作
            while (top && stk[top].x == 1) q = min(q, stk[top --].y); // 两个连续的后缀操作，保留较小的
            while (top >= 2 && stk[top - 1].y >= q) top -= 2; // 删掉前面的同类操作
            stk[ ++ top] = {1, q}; // 记录当前操作
        }
    }

    int k = n, l = 1, r = n;
    for (int i = 1; i <= top; i ++) { // 从前往后处理一下所有的询问
        if (stk[i].x == 0) // 前缀：该区间的右端点是可以固定的
            while (r > stk[i].y && l <= r) ans[r --] = k --;
        else // 同理
            while (l < stk[i].y && l <= r) ans[l ++] = k --;
        if (l > r) break; // 表示区间为空了    
    }

    if (top % 2) // 如果操作数是奇数, 做完了右区间，还剩一个左区间
        while (l <= r) ans[l ++] = k --;
    else // 如果操作数是偶数, 做完了左区间，还剩一个右区间
        while (l <= r) ans[r --] = k --;

    for (int i = 1; i <= n; i ++) cout << ans[i] << ' ';
    return 0;
}