CF631C Report

每个月，Blake 都会收到一份包含公司 “Blake Technologies” 主要经济指标的报告。公司共生产 $n$ 种商品，每种商品在最终报告中都有且仅有一个整数，表示其对应的营收。在送到 Blake 手中之前，这份报告会经过 $m$ 个经理人之手。每个经理会按照某种顺序对部分内容重新排序。具体来说，第 $i$ 个经理会对前 $r_i$ 个数进行排序：如果 $t_i=1$，则按非递减顺序排序；如果 $t_i=2$，则按非递增顺序排序。然后他会将整理后的报告交给下一位经理（即第 $i+1$ 位），或者直接交给 Blake（如果他是第 $m$ 个经理）。 “Blake Technologies” 的员工正在准备这份报告。你知道初始的序列 $a_i$（长度为 $n$），以及每位经理人的操作描述 $t_i$ 和 $r_i$。请你帮助加快这个过程，并确定经过所有经理之后，送到 Blake 手中的最终报告内容。

第一行输入两个整数 $n$ 和 $m$（$1 \leq n, m \leq 200000$）——报告中商品的数量和经理的数量。 第二行输入 $n$ 个整数 $a_i$（$|a_i| \leq 10^9$），即初始的报告内容。 接下来有 $m$ 行，每行描述一位经理的操作。第 $i$ 行包含两个整数 $t_i$ 和 $r_i$（$1 \leq t_i \leq 2, 1 \leq r_i \leq n$），表示第 $i$ 位经理会将前 $r_i$ 个数按照非递减顺序（若 $t_i=1$）或非递增顺序（若 $t_i=2$）排序。

输出 $n$ 个整数，为最终由第 $m$ 位经理交到 Blake 手中的报告内容。

在第一个样例中，初始报告为：1 2 3。经过第一个经理后，前两个数交换了：2 1 3。报告以此形式交到 Blake 手中。 在第二个样例中，初始报告为：1 2 4 3。经过第一个经理后变为：4 2 1 3。经过第二个经理后变为：2 4 1 3。最终以此形式交给 Blake。 由 ChatGPT 5 翻译