HDU6592 Beauty Of Unimodal Sequence

            Beauty Of Unimodal Sequence

            给一个序列,在满足单调递增或者单调递减或者先增后减的最长子序列集合里找到下标字典序最大以及最小的两个子序列,输出这两个子序列里元素的下标。

            n≤3×105

            moomhxy的题解

            先正着求一遍LIS,再反着求一遍LIS,求出每个点作为上升子序列结尾的最大长度和每个点作为下降子序列开头的最大长度。

            我们可以枚举这个单峰序列的峰顶是什么,这样最长长度就找到了。

            然后考虑怎么构造解。

            求字典序最小的话,首先找到第一个顶峰,然后往前找递减的序列中下标较小的,往后就依次找,这样能保证字典序最小。

            如何找这个下标较小的呢?显然我们希望每种结尾长度的点都越靠前越好。所以用单调栈维护即可。

            最大的话找到最后一个顶峰,往前是依次找,往后是找LIS中下标大的。维护方法类似。

            时间复杂度 O(n log n),瓶颈在于求LIS。

            CO int N=300000+10;
            int a[N],dp[N],up[N],down[N];
            int h[N],st[N],ans[N];
            
            void real_main(int n){
                fill(dp,dp+n+1,INT_MAX),dp[0]=0;
                for(int i=1;i<=n;++i){
                    read(a[i]);
                    up[i]=lower_bound(dp+1,dp+n+1,a[i])-dp;
                    dp[up[i]]=a[i];
                }
                fill(dp,dp+n+1,INT_MAX),dp[0]=0;
                for(int i=n;i;--i){
                    down[i]=lower_bound(dp+1,dp+n+1,a[i])-dp;
                    dp[down[i]]=a[i];
                }
                // minimum lexicographic order
                int tot=0;
                int peak=1,height=up[1]+down[1];
                for(int i=2;i<=n;++i)
                    if(up[i]+down[i]>height) peak=i,height=up[i]+down[i];
                int top=0;
                h[up[peak]]=a[peak];
                for(int i=peak-1;i;--i){
                    if(a[i]>=h[up[i]+1]) continue;
                    while(top and up[i]>=up[st[top]]) --top;
                    st[++top]=i;
                    h[up[i]]=a[i];
                }
                for(;top;--top) ans[++tot]=st[top];
                ans[++tot]=peak;
                for(int i=peak+1;i<=n;++i)
                    if(down[i]==down[ans[tot]]-1 and a[i]<a[ans[tot]]) ans[++tot]=i;
                for(int i=1;i<=tot;++i) printf("%d%c",ans[i]," \n"[i==tot]);
                // maximum lexcographic order
                tot=0;
                peak=1,height=up[1]+down[1];
                for(int i=2;i<=n;++i)
                    if(up[i]+down[i]>=height) peak=i,height=up[i]+down[i];
                top=0;
                st[++top]=peak;
                for(int i=peak-1;i;--i)
                    if(up[i]==up[st[top]]-1 and a[i]<a[st[top]]) st[++top]=i;
                for(;top;--top) ans[++tot]=st[top];
                h[down[peak]]=a[peak];
                for(int i=peak+1;i<=n;++i){
                    if(a[i]>=h[down[i]+1]) continue;
                    while(tot and down[i]>=down[ans[tot]]) --tot;
                    ans[++tot]=i;
                    h[down[i]]=a[i];
                }
                for(int i=1;i<=tot;++i) printf("%d%c",ans[i]," \n"[i==tot]);
            }
            int main(){
                for(int n;~scanf("%d",&n);) real_main(n);
                return 0;
            }

            HDU什么时候开始支持<bits/stdc++.h>了……

            相关文章
            相关标签/搜索
            2020王中王资料一肖中2018年香港开奖日期表2018香港历史开奖结果香港最快开奖现场直播 虎林市| 灌云县| 遵义县| 湄潭县| 南充市| 罗山县| 婺源县| 枞阳县| 阳泉市| 大方县| 黄山市| 恩平市| 浮山县| 锡林郭勒盟| 寻甸| 祁东县| 寿光市| 冀州市| 宝山区| 朔州市| 清水河县| 镇赉县| 榆林市| 屯门区| 曲阜市| 浑源县| 陆河县| 灵台县| 巴林左旗| 根河市| 平邑县| 荣昌县| 石屏县| 彰化县| 东丽区| 买车| 峨山| 保定市| 曲周县| 邢台县| 平乐县| 玛纳斯县| 康马县| 芮城县| 江阴市| 孝感市| 宁波市| 东莞市| 皋兰县| 台山市| 德安县| 庆元县| 平谷区| 西乡县| 永康市| 奎屯市| 玉山县| 平利县| 邮箱| 钟山县| 汉沽区| 太仆寺旗| 武功县| 新宾| 资阳市| 三明市| 阿城市| 曲周县| 庆城县| 西充县| 东至县| 汉阴县| 濉溪县| 饶平县| 苗栗市| 辉南县| 长垣县| 上林县| 曲水县| 隆昌县| 林周县| 卢氏县| 乳山市| 光山县| 顺昌县| 台中市| 博湖县| 来凤县| 托克逊县| 丹巴县| 普兰店市| 南昌县| 遵义市| 九龙县| 西畴县| 陕西省| 靖边县| 天柱县| 上林县| 湖南省| 周宁县| 新乐市| 民县| 监利县| 北川| 德保县| 新平| 无棣县| 北流市| 铜梁县| 青海省| 北辰区| 岱山县| 鸡东县| 滦平县| 肃宁县| 金塔县| 龙海市| 榆林市| 桐城市| 怀柔区| 韶关市| 乳源| 嘉义县| 延吉市| 从化市| 八宿县| 昭通市| 安康市| 深州市| 根河市| 武山县| 洪江市| 容城县| 叶城县| 德阳市| 清河县| 宁远县| 玛多县| 昆山市| 嘉祥县| 库车县| 瑞安市| 绥宁县| 正阳县| 赣州市| 高密市| 曲松县| 萨迦县| 边坝县| 信宜市| 左权县| 敦化市| 西昌市| 达拉特旗| 进贤县| 铜川市| 和林格尔县| 同德县| 闸北区| 鹤壁市| 新安县| 揭西县| 邵阳市| 屏山县| 金沙县| 鹤山市| 安远县| 子洲县| 通江县| 桐庐县| 拉萨市| 睢宁县| 京山县| 若尔盖县| 鄢陵县| 六盘水市| 泸定县| 钟祥市| 甘谷县| 辉县市| 金乡县| 东宁县| 临夏县| 中山市| 宝清县| 米林县| 青岛市| 七台河市| 潜江市| 普洱| 广河县| 延吉市| 曲麻莱县| 安西县| 锦州市| 长沙市| 枝江市| 修水县| 平顶山市| 大冶市| 福建省| 二连浩特市| 农安县| 林芝县| 东乌珠穆沁旗| 禄劝| 嘉荫县| 五华县| 尖扎县| 静安区| 衡南县| 台湾省| 左云县| 凤城市| 宝坻区| 台南市| 西贡区| 呼伦贝尔市| 车险| 建湖县| 彰化县| 通山县| 肃南| 怀远县| 双城市| 新兴县| 巧家县| 芷江| 资中县| 安岳县| 伊宁县| 昭平县| 大邑县| 来凤县| 正镶白旗| 云安县| 宁阳县| 吐鲁番市| 阿鲁科尔沁旗| 隆子县| 钟祥市| 连山| 铁岭市| 宁波市| 恩平市| 揭西县| 从化市| 安化县| 建阳市| 鹤岗市| 安宁市| 自贡市| 仙桃市| 无为县| 辽源市| 久治县| 北安市| 曲松县| 墨玉县| 吉林省| 赤壁市| 卢龙县| 洪江市| 华坪县| 资中县| 六盘水市| 乐陵市| 沅陵县| 安化县| 灵台县| 商城县| 中西区| 崇义县| 紫金县| 景东| 金川县| 滦平县| 巢湖市| 凤庆县| 瓦房店市| 康保县| 穆棱市| 侯马市| 松桃| 宜城市| 郁南县| 遂溪县| 舞阳县| 甘肃省| 政和县| 红河县| 临猗县| 秭归县| 盐亭县| 永新县| 红安县| 黄陵县| 商洛市| 木里| 伊宁市| 正蓝旗| 上虞市| 清徐县| 平凉市| 蕲春县| 牡丹江市| 和硕县| 莒南县| 太保市| 乌兰察布市| 西和县| 红安县| 巧家县| 手游| 房产| 崇文区| 房产| 皮山县| 旅游| 德保县| 钟祥市| 平阳县| 台北市| 扶绥县| 凤台县| 蓬莱市| 攀枝花市| 新宾| 临清市| 洛川县| 泗洪县| 黔西县| 浮山县| 鄂托克旗| 漳州市| 晴隆县| 都安| 府谷县| 保亭| 酒泉市| 陇川县| 陆良县| 安化县| 温州市| 大港区| 雷山县| 鱼台县| 嘉定区| 沅江市| 临颍县| 边坝县| 镇宁| 镇安县| 温泉县| 翁牛特旗| 昌乐县| 托克逊县| 杭锦旗| 四子王旗| 阜新市| 台东市| 甘孜| 太康县| 兰西县| 阿克陶县| 五常市| 大兴区| 台州市| 陆河县| 耿马| 萨嘎县| 三都| 格尔木市| 赤城县| 壶关县| 长海县| 民和| 松阳县| 嵊泗县| 包头市| 丰都县| 柳林县| 柳江县| 木里| 湘西| 应用必备| 兰西县| 黄冈市| 赫章县| 班玛县| 隆化县| 吴堡县| 瓮安县| 南澳县| 云霄县| 张北县| 凯里市| 白水县| 柘荣县| 柯坪县| 宁津县| 焉耆| 昭苏县| 望江县| 鹤山市| 柳林县| 瑞昌市| 濮阳市| 岳阳县| 台州市| 清流县| 无锡市| 邳州市| 武川县| 卢龙县| 酒泉市| 自贡市| 周宁县| 和平区| 洞口县| 扶余县| 西宁市| 昌图县| 鱼台县| 察雅县| 赤水市| 黄龙县| 娄烦县| 乌兰察布市| 平湖市| 丹阳市| 军事| 措美县| 灵山县| 瓦房店市| 恩平市| 根河市| 镇巴县| 桐梓县| 博客| 芜湖市| 资源县| 阿克苏市| 安图县| 洛阳市| 贺州市| 蒙山县| 湘潭县| 横峰县| 会昌县| 盘山县| 吉木萨尔县| 阿克苏市| 邵东县| 永泰县| 乐东| 贵溪市| 隆德县| 濉溪县| 嘉黎县| 高碑店市| 邓州市| 望谟县| 丰台区| 板桥市| 乐东| 贡觉县| 修文县| 湘潭县| 当涂县| 丰县| 天全县| 永安市| 天全县| 松阳县| 大英县| 泊头市| 平潭县| 武城县| 南投县| 克什克腾旗| 乐业县| 稻城县| 株洲县| 永泰县| 台湾省| 陆良县| 定日县| 定安县| 阳东县| 鸡泽县| 房产| 招远市| 宕昌县| 新密市| 治多县| 金门县| 广汉市| 屏东市| 桃园市| 沽源县| 大洼县| 泰和县| 泌阳县| 团风县| 隆安县| 扬中市| 财经| 昭觉县| 石城县| 万全县| 湘潭市| 剑川县| 屏东县| 德阳市| 平泉县| 濉溪县| 青神县| 砚山县| 榕江县| 蓬溪县| 墨脱县| 长寿区| 西平县| 祁门县| 泾源县| 蒲城县| 舞钢市| 博乐市| 平武县| 琼中| 蛟河市| 雅江县| 武义县| 博罗县| 海宁市| 宜章县| 萨迦县| 航空| 山西省| 通化县| 满洲里市| 芜湖县| 益阳市| 吉林市| 房产| 白玉县| 建宁县| 尼勒克县| 商丘市| 琼中| 庐江县| 双牌县| 新巴尔虎左旗| 独山县| 体育| 车致| 南平市| 奉节县| 略阳县| 榕江县| 县级市| 文安县| 手游| 中宁县| 禹城市| 察哈| 天门市| 余姚市| 黄陵县| 朝阳区| 金坛市| 双牌县| 渭南市| 马鞍山市| 佛冈县| 定边县| 岚皋县| 云阳县| 瑞昌市| 清河县| 图木舒克市| 阿克苏市| 得荣县| 梁山县| 满城县| 屯昌县| 华容县| 桃园县| 大姚县| 印江| 巴东县| 玛曲县| 伊宁市| 周至县| 曲周县| 根河市| 仁化县| 邵东县| 汉川市| 来安县| 连云港市| 隆林| 临武县| 依兰县| 青龙| 汝州市| 花莲县| 清远市| 平阳县| 丹寨县| 宽甸| 梨树县| 曲阜市| http://dwujjp.fit http://m.jmggng.fit http://www.gjtuil.fit http://www.yyoqma.fit http://wtntrt.fit http://www.rwkptl.fit http://wap.nxbzgz.fit http://m.bm1961openz.fit http://otffih.fit http://www.likzvv.fit http://www.bm1961xeterz.fit http://mekhpk.fit http://qeherz.fit http://www.yqxdml.fit http://wap.psvyvl.fit http://m.kexsdn.fit http://wap.ldwmiq.fit http://zofqai.fit