思路：
如果有两次操作i和j，j在i后面操作，且j的x比i的x大，则i的操作被j所覆盖（即i的操作是无用的）
可以将操作i删除。
如果有两次操作i和j，j在i后面操作，且j的x比i的x小，则需要按顺序操作ij。
所以使用单调递减栈来优化
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, ans, a[N], b[N], top;
// 数组模拟单调栈
struct node
{int k, x;
} st[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = a[i];}while (m--){ // 单调栈，去除无效操作int k, x;cin >> k >> x;while (top && st[top].x <= x)top--;st[++top] = {k, x};}int nn = st[1].x; // 取栈底元素sort(b + 1, b + nn + 1);int l = 1, r = nn;st[top + 1].x = 0;for (int i = 1; i <= top; i++){int t = st[i].x - st[i + 1].x;if (st[i].k == 1)while (t--)a[nn--] = b[r--];elsewhile (t--)a[nn--] = b[l++];}for (int i = 1; i <= n; i++){cout << a[i] << " ";}return 0;
}
