#4980. [HEOI2016/TJOI2016] 排序

    ID: 4980 远端评测题 4000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2016线段树二分各省省选河北排序

[HEOI2016/TJOI2016] 排序

题目描述

20162016 年,佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题,现在她在研究一个难题,需要你来帮助她。

这个难题是这样子的:给出一个 11nn 的排列,现在对这个排列序列进行 mm 次局部排序,排序分为两种:

  • 0 l r 表示将区间 [l,r][l,r] 的数字升序排序
  • 1 l r 表示将区间 [l,r][l,r] 的数字降序排序

注意,这里是对下标在区间 [l,r][l,r] 内的数排序。
最后询问第 qq 位置上的数字。

输入格式

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

第二行为 nn 个整数,表示 11nn 的一个排列。

接下来输入 mm 行,每一行有三个整数 op,l,r\text{op},l,rop\text{op}00 代表升序排序,op\text{op}11 代表降序排序, l,rl,r 表示排序的区间。

最后输入一个整数 qq,表示排序完之后询问的位置

输出格式

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

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

提示

河北省选2016第一天第二题。

对于 30%30\% 的数据,n,m1000n,m\leq 1000

对于 100%100\% 的数据,n,m105n,m\leq 10^51qn1\leq q\leq n