首页 > 题解 > luogu2824 [HEOI2016]排序

luogu2824 [HEOI2016]排序

记一道不错的二分

题目描述

在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

输入输出格式

输入格式:
输入数据的第一行为两个整数n和m。n表示序列的长度,m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整数,表示1到n的一个全排列。接下来输入m行,每一行有三个整数op, l, r, op为0代表升序排序,op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q,q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5,1 <= m <= 10^5

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

输入输出样例

输入样例#1: 复制
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
输出样例#1: 复制
5
说明

河北省选2016第一天第二题。原题的时限为6s,但是洛谷上是1s,所以洛谷的数据中,对于30%的数据,有 n,m<=1000,对于100%的数据,有 n,m<=30000

思路:

一开始一直在想数据结构直接维护。但因为昨天刚做个比赛有道二分答案,立刻就想出来了。

因为是全排列,可以在1-n里面二分答案。找到答案以后就把原序列里面大于它的赋成1,小于的变成0。这样排序就可以用两个区间覆盖代替。总的效率$O(m \log^2 n)$

代码:


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×