9273 - 数列排序

在今年,小明的姐姐喜欢上了数字序列。所以她经常研究关于序列的一些奇奇怪怪的问题,现在她在研究一个难题,需要你来帮助她。 这个难题是这样的:给出一个排列,这个序列有n个数,现在对这个排列序列进行m次局部排序的操作,排序分为两种: 0 l r表示将区间的数字升序排序; 1 l r表示将区间的数字降序排序; 注意,这里是对下标在区间[l,r]内的数排序。 m次操作后,最后询问第q位置上的数字。

输入

输入数据的第一行为两个整数nmn表示序列的长度,m表示局部排序的次数。 第二行为n个整数,表示排列的具体数值。 接下来输入m行,每一行有三个整数op,l,r,op为0代表升序排序,op为1代表降序排序,l,r表示排序的区间。 最后输入一个整数q,表示排序完之后询问的位置。

输出

输出数据仅有一行,一个整数,表示按照顺序将全部的部分排序结束后第 q 位置上的数字。

样例

输入

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

输出

5

提示

对于样例1: 初始序列为[1,6,2,5,3,4]。 op=0,对[1,4]区间进行升序后,序列为[1,2,5,6,3,4]; op=1,对[3,6]区间进行降序后,序列为[1,2,6,5,4,3]; op=0,对[3,4]区间进行升序后,序列为[1,2,5,6,4,3]; 最后查询第三个位置的数为:5 。

n,m \leq \gdef\foo#1{#1^5} \foo{10}

1 \leq q \leq n

来源

云南编程挑战赛

时间限制 2 秒
内存限制 128 MB
讨论 统计
上一题 下一题