TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7342
  • 题目
  • P7342「TJOI / HEOI2016」排序
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

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

    这个难题是这样子的:给出一个 \(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}\)0 代表升序排序,\(\text{op}\)1 代表降序排序, \(l, r\) 表示排序的区间。
    最后输入一个整数 \(q\)\(q\) 表示排序完之后询问的位置,$1 \leq q \leq n$。

    输出格式

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

    样例输入

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

    样例输出

    3