善良的hzwer

2014年8月17日1,3950

同公主的工作

由于本题难度太高,善良的hzwer说:“为了方便旅客串门,还是将他们的房间安排为相邻的一排为好233。”

对于每一天输出一行依次代表选取的房间高度,房间必须相邻,若不能安排则输出 Impossible。(为了减少输出所需时间,只需输出第一个数即可)

因为在做wulala的神模拟赛的时候题目看错了就出了这么一题

T T

做法是求出每个点为开头向后的连续上升序列长度

然后可以搞一个答案数组T T,比如以字典序最小的数x1开头的长度为ans1,以此类推,则1-ans1的答案为x1,接着确定ans1-ans2的答案为x2(若ans2>ans1),然后把所有数扫一遍,处理出答案数组,O1回答询问

复杂度nlogn+m

以上是wt神犇的解法

作为一个逗比出题人,我想到的解法是按照上升序列长度从小到大扔进单调栈中,栈中是字典序单调递增,每次询问在栈中二分

复杂度(n+m)logn