BZPRO

#5042. LWD的分科岛

内存限制：256 MiB 时间限制：8 Sec
提交 提交记录 讨论

题目描述

大家都知道在文理分科的时候总是让人纠结的，纠结的当然不只是自己。比如 YSY 就去读了文科， LWD 知道了很
气。于是他就去卡了 BZOJ 测评机， 晚上他做了一个谜一样的梦，自己在一座全是 YSY 的分科岛。这里有 YSY 
草， YSY 花， YSY 糖……每个 YSY 都有一个美（ Ti）丽（ Zhong）值。当然没有小于零的体重啦！LWD 于是不
惜重金卖肉想买下这座岛，可是分科岛的岛主，是一位忠实的区间问题爱好者。他想把小岛传给一个谜一样的爱好
者，所以岛主给了 LWD 一个终极挑战——选出一片区域中最美丽的 YSY。可是岛主的审美观不像 YYR那么专一，
他有时喜欢现代美——最轻的，有时喜欢唐代美——最重的。这让被欢喜冲昏了头脑（血液集中在下半身）的 LWD
 十分苦恼。他要在规定时间内完成挑战赢得买岛的权利，于是只有求助 DalaoYYR，可是 YYR 要准备课件啊。只
有比 YYR 弱很多的你能够帮他了。挑战内容如下岛主将把 N 个 YSY 摆成一个条形，并给出所有 YSY 的美丽值。
挑出多少个就要看岛主心情了，他觉得 LWD 是条汉子就会给出很多很多的 YSY 满足他。岛主将给出 Q 个考验，
询问内容是在给定区间内求出最美丽的 YSY。你已经了解规则了，开始你的表演吧！

输入格式

第一行为一个整数 N，表示岛主摆出了 N 个 YSY。
接下来一行 N 个整数，表示每个 YSY 的美丽值(单位：kg)，因为 YSY 整体很美所以 YSY
不会超过 1019kg。
接下来一行一个整数 Q，表示岛主有 Q 个考验。Q<=1500000
接下来 Q 行，每行三个整数 opt, l, r 。 opt 等于 1 时表示岛主那时喜欢现代美，等于 2
时代表岛主那时喜欢唐代美。询问最美计划在区间[l, r]中进行
100%的数据 N<= 3000000, 美丽值不会超过 1019， Q<= 150000 
数据量巨大，请优化读入

输出格式

每一行对于每个考验输出结果，以回车符结束。

样例

样例输入


			
5 5

1 2 3 4 5

1 1 2

2 1 3

1 2 5

2 4 5

2 1 5

样例输出


			
1 

3 

2 

5 

5

数据范围与提示

注意：为减轻主站压力，本题完整版请到http://begin.lydsy.com/JudgeOnline/problem.php?id=4191进行提交，带来不便，敬请谅解。


BZPRO Powered by Remmina.
Github Repository