#2407. 排序

排序

排序

题目描述

NOI 2016天津市代表队选拔赛day1 B 排序 • 输入输出文件: sort.in/sort.out • 源文件名: sort.cpp/sort.c/sort.pas • 时间限制: 6s 内存限制: 256M 题目描述 在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些 奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。 这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进 行m次局部排序,排序分为两种: • (0, l, r)表示将区间[l, r]的数字升序排序 • (1, l, r)表示将区间[l, r]的数字降序排序 最后询问第q位置上的数字。 输入 输入数据的第一行为两个整数n和m。n表示序列的长度,m表示局部排序的 次数。1 ≤n, m ≤105 第二行为n个整数,表示1到n的一个全排列。 接下来输入m行,每一行有三个整数op, l, r, op为0代表升序排序,op为1代 表降序排序, l, r 表示排序的区间。 最后输入一个整数q,q表示排序完之后询问的位置, 1 ≤q ≤n。 输出 输出数据仅有一行,一个整数,表示按照顺序将全部的部分排序结束后 第q位置上的数字。 样例输入 6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3 样例输出 5 4

NOI 2016天津市代表队选拔赛day1 数据范围 对于30%的数据,1 ≤n ≤100,1 ≤m ≤100 对于100%的数据,1 ≤n ≤105,1 ≤m ≤105 5

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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