题解 | #随机序列#

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define fi first
#define se second

using namespace std;

const int N = 2e5 + 10;

int a[N];
int x[N], t[N];
vector<pair<int, int>> st;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> t[i] >> x[i];
	
	int mx = 0;
	// 对于数组a, [1, x[maxi]] 排序完之后，得再排序 [1, x[se-maxi]], 然后再排 [1, x[th-maxi]]，以此类推。
	// 会发现从前往后找，对于数组x, 要先遍历区间[1, m], 找到 max，再记录下 maxi，再将 mx 归 0。然后再遍历区间[maxi + 1, m]，再找一个最大值 se-max，再把下标 se-maxi 记录下来，然后再遍历[se-maxi + 1, m], 一直不断遍历下去，有点像归并排序只处理右孩子区间一样，时间复杂度肯定超 O(N)了。
	// 但从后往前找，对于数组x，mx 就不用归 0, 找的时候，先把 x[m]赋给 mx, (a[x[m]]在后续操作中会在最后一次排序操作中被单独排序),再把 x[m] 记录下来，往前遍历，如果x[i] <= mx, 说明在数组a中[1, x[i]]的元素排序操作会被 sort(a + 1, a + mx + 1) 或 sort(a + 1, a + mx + 1, greater<int>()) 覆盖掉；如果 x[i] > mx，说明在数组a中[1, x[i]]包括的元素要比[1, mx]还要多，记录下来，放到倒数第二次排序，继续往前遍历。只需遍历一遍，就把需要排序的区间给倒着存好了，时间复杂度为 O(N)。
	for(int i = m; i >= 1; i--) {
		if(mx < x[i]) {
			st.push_back({t[i], x[i]});
			mx = x[i];
		}
	}
	
	for(int i = st.size() - 1; i >= 0; i--) {
		int t = st[i].fi, x = st[i].se;
		if(t == 1) sort(a + 1, a + x + 1);
		else sort(a + 1, a + x + 1, greater<int>());
	}
	
	for(int i = 1; i <= n; i++) cout << a[i] << " ";
	
	return 0;
}
// 附：x[maxi]为数组x在[1, m]范围内元素最大值，x[se-maxi]为数组x在[maxi + 1, m]元素最大值，x[th-maxi]为数组x在[se-maxi, m]元素最大值，以此类推。