#1083. 「TJOI / HEOI2016」排序

内存限制:256 MiB 时间限制:4000 ms 输入文件:sort.in 输出文件:sort.out
题目类型:传统 评测方式:文本比较
上传者: Handwer

题目描述

给出一个 1 到 n 的全排列,现在对这个全排列序列进行 m 次局部排序,排序分为两种:

  1. (0, l, r) 表示将区间 [l, r] 的数字升序排序
  2. (1, l, r) 表示将区间 [l, r] 的数字降序排序

排序后询问第 q 位置上的数字。

输入格式

输入数据的第一行为两个整数 n 和 m,n 表示序列的长度,m 表示局部排序的次数。

第二行为 n 个整数,表示 1 到 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

数据范围与提示

对于 30% 的数据,n,m ≤ 1000

对于 100% 的数据,n,m ≤ 100000,1 ≤ q ≤ n