C38 线段树+二分[HEOI2016/TJOI2016] 排序
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
[AdditionalFile2055.zip](file://AdditionalFile2055.zip?type=additional_file)
#2055. 「TJOI / HEOI2016」排序
标签: 传统 | 时间限制: 6000 ms | 内存限制: 256 MiB |
题目描述
在 2016 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。
这个难题是这样子的：给出一个 到 的全排列，现在对这个全排列序列进行 次局部排序，排序分为两种：
- 表示将区间 的数字升序排序
- 表示将区间 的数字降序排序
排序后询问第 位置上的数字。
输入格式
输入数据的第一行为两个整数 和 。 表示序列的长度， 表示局部排序的次数 ()。
第二行为 个整数，表示 到 的一个全排列。
接下来输入 行，每一行有三个整数 ， 为 0 代表升序排序， 为 1 代表降序排序, 表示排序的区间。
最后输入一个整数 ， 表示排序完之后询问的位置，。
输出格式
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 位置上的数字。
样例
输入
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
输出
5