Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

05/12
09:51
二分法 线段树

[bzoj 4552] Tjoi2016&Heoi2016 排序

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入数据的第一行为两个整数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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

5

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

考虑二分答案 对于mid,把所有大于mid的数变为1,小于mid的数变成0,于是排序就变成了统计区间内1的个数和区间赋值,用线段树来维护,最后判断一下就行了

c++:

pascal:

 

[bzoj 4552] Tjoi2016&Heoi2016 排序