A5712. 「TJOI / HEOI2016」排序
编程题
省选/NOI-
知识点
题目描述
在 2016 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。
这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：
1. $(0, l, r)$ 表示将区间 $[l, r]$ 的数字升序排序
2. $(1, l ,r)$ 表示将区间 $[l, r]$ 的数字降序排序
排序后询问第 $q$ 位置上的数字。
这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：
1. $(0, l, r)$ 表示将区间 $[l, r]$ 的数字升序排序
2. $(1, l ,r)$ 表示将区间 $[l, r]$ 的数字降序排序
排序后询问第 $q$ 位置上的数字。
输入格式
输入数据的第一行为两个整数 $n$ 和 $m$。$n$ 表示序列的长度，$m$ 表示局部排序的次数 ($1 \leq n, m \leq 10^5$)。
第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个全排列。
接下来输入 $m$ 行，每一行有三个整数 $\text{op}, l, r$， $\text{op}$ 为 `
最后输入一个整数 $q$，$q$ 表示排序完之后询问的位置，$1 \leq q \leq n$。
第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个全排列。
接下来输入 $m$ 行，每一行有三个整数 $\text{op}, l, r$， $\text{op}$ 为 `
0 代表升序排序，$\text{op}$ 为 1` 代表降序排序, $l, r$ 表示排序的区间。最后输入一个整数 $q$，$q$ 表示排序完之后询问的位置，$1 \leq q \leq n$。
输出格式
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 位置上的数字。
输入输出样例
输入 #1
6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3
输出 #1
5