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>了……

            相关文章
            相关标签/搜索
            王中王鉄算好开奖结果四肖期期准铁算盘4887开奖结果四肖三期内必出刘伯温6374cm刘伯温168最快开奖现场开马开奖结果 阿瓦提县| 乐安县| 大丰市| 江北区| 瑞安市| 运城市| 赤城县| 开阳县| 庆安县| 三明市| 康保县| 青龙| 绥芬河市| 尚志市| 古蔺县| 黄浦区| 枣强县| 德庆县| 太原市| 香河县| 三亚市| 云和县| 林周县| 视频| 财经| 怀柔区| 扶沟县| 翁牛特旗| 石景山区| 得荣县| 沧州市| 黄梅县| 咸丰县| 梁河县| 钟山县| 梧州市| 托里县| 临桂县| 湖口县| 彩票| 布尔津县| 安达市| 保康县| 东乌珠穆沁旗| 扶绥县| 金平| 谷城县| 北安市| 沧源| 承德县| 巴林左旗| 冀州市| 安仁县| 长岛县| 海门市| 江华| 辉南县| 阳江市| 苗栗县| 定州市| 崇义县| 阿鲁科尔沁旗| 台山市| 高要市| 泌阳县| 拉萨市| 宁乡县| 二手房| 仪陇县| 图片| 漳平市| 安丘市| 醴陵市| 松阳县| 城步| 定西市| 浪卡子县| 正安县| 黄浦区| 蒙山县| 前郭尔| 铜鼓县| 昂仁县| 都昌县| 略阳县| 柯坪县| 东辽县| 拜泉县| 浦城县| 七台河市| 余姚市| 洛南县| 韶山市| 墨脱县| 应用必备| 新化县| 石屏县| 富裕县| 顺平县| 博湖县| 天全县| 衡东县| 南京市| 沁水县| 谢通门县| 湛江市| 交口县| 高台县| 永新县| 蕉岭县| 富川| 西青区| 栖霞市| 肥西县| 宁德市| 衢州市| 西贡区| 平定县| 图片| 镇远县| 枣强县| 辽阳市| 遂溪县| 青海省| 巴林右旗| 岫岩| 财经| 沙湾县| 平遥县| 邢台县| 苏州市| 司法| 屯昌县| 苏尼特左旗| 保定市| 讷河市| 三台县| 徐水县| 兖州市| 娄底市| 仪陇县| 工布江达县| SHOW| 外汇| 高邑县| 弋阳县| 嘉义县| 华安县| 凤山县| 和田县| 无为县| 建德市| 甘南县| 呼图壁县| 蒲城县| 千阳县| 康马县| 亳州市| 剑河县| 大悟县| 甘南县| 申扎县| 滦平县| 南丰县| 监利县| 宜宾县| 湘潭市| 邹平县| 漳平市| 平果县| 衡山县| 海阳市| 台中县| 林周县| 福清市| 离岛区| 瑞安市| 马龙县| 焉耆| 五大连池市| 察隅县| 吉隆县| 黎平县| 隆昌县| 庆元县| 比如县| 诸城市| 石嘴山市| 霍林郭勒市| 镇原县| 邛崃市| 新沂市| 确山县| 平远县| 广汉市| 秭归县| 宜城市| 河源市| 全椒县| 朔州市| 邢台县| 许昌市| 金平| 澄城县| 瑞安市| 香格里拉县| 开原市| 南通市| 农安县| 双城市| 黎川县| 五大连池市| 潮州市| 大渡口区| 中卫市| 南阳市| 邳州市| 昭通市| 抚远县| 进贤县| 九龙坡区| 碌曲县| 汽车| 兴文县| 镇平县| 和龙市| 井冈山市| 游戏| 鄂伦春自治旗| 若尔盖县| 绥滨县| 枣阳市| 织金县| 大余县| 栾城县| 双桥区| 扎赉特旗| 洪泽县| 宿州市| 长春市| SHOW| 永年县| 临夏市| 湘乡市| 安西县| 通许县| 柯坪县| 固阳县| 武冈市| 固阳县| 临朐县| 石渠县| 柏乡县| 平定县| 吉木乃县| 浦城县| 扶余县| 乌鲁木齐县| 弥勒县| 绩溪县| 高陵县| 正镶白旗| 中西区| 宣城市| 义马市| 怀集县| 堆龙德庆县| 文安县| 甘南县| 呼玛县| 井陉县| 潼南县| 胶州市| 绥滨县| 尖扎县| 临海市| 建水县| 莲花县| 东丽区| 依兰县| 太湖县| 增城市| 乐至县| 滕州市| 龙川县| 乐山市| 济南市| 神木县| 鹰潭市| 甘泉县| 晋江市| 福泉市| 乳山市| 志丹县| 太仆寺旗| 页游| 盐源县| 时尚| 茶陵县| 永吉县| 曲阳县| 绥化市| 金昌市| 镇康县| 金湖县| 花垣县| 法库县| 昆明市| 中超| 台前县| 安宁市| 尼玛县| 通化市| 金门县| 通化县| 涞源县| 富川| 乐平市| 张北县| 武胜县| 邮箱| 闻喜县| 双鸭山市| 齐齐哈尔市| 中卫市| 湘西| 贞丰县| 麻江县| 余庆县| 贡嘎县| 巴中市| 额济纳旗| 涟源市| 柳河县| 镇原县| 常熟市| 丁青县| 玉环县| 临邑县| 淮南市| 沅陵县| 宜宾市| 满城县| 晋州市| 岐山县| 寻乌县| 泗阳县| 乌兰察布市| 沁水县| 兴安县| 九台市| 徐闻县| 开江县| 崇礼县| 绵竹市| 西安市| 漠河县| 吉安市| 九江市| 遂昌县| 惠东县| 永安市| 馆陶县| 平江县| 分宜县| 图木舒克市| 祁阳县| 洛扎县| 九龙城区| 开江县| 库车县| 冀州市| 海林市| 山东省| 湛江市| 通城县| 阿巴嘎旗| 石渠县| 休宁县| 沙雅县| 孙吴县| 留坝县| 洛扎县| 申扎县| 哈密市| 南木林县| 翁源县| 道孚县| 桂阳县| 无锡市| 敖汉旗| 临西县| 西畴县| 射阳县| 渑池县| 连南| 宣汉县| 忻州市| 绵竹市| 清水河县| 交口县| 辽源市| 瑞昌市| 临城县| 吉木乃县| 蒲城县| 绿春县| 七台河市| 洪雅县| 上虞市| 霸州市| 遵义县| 双鸭山市| 金坛市| 宁德市| 双峰县| 子洲县| 湟中县| 威信县| 石嘴山市| 武宣县| 仙居县| 辽宁省| 合阳县| 沂南县| 新巴尔虎右旗| 汶川县| 深州市| 原阳县| 花莲市| 屏东市| 金塔县| 中宁县| 阿克| 金昌市| 黄平县| 江门市| 宿松县| 夏河县| 蒲江县| 婺源县| 黄骅市| 峨眉山市| 屏东县| 广州市| 成都市| 宁强县| 林芝县| 阳朔县| 远安县| 兰西县| 靖宇县| 黔西| 西华县| 曲周县| 航空| 太和县| 大关县| 岐山县| 股票| 包头市| 巩义市| 桂阳县| 尼玛县| 兰州市| 怀来县| 澄城县| 夏邑县| 杭锦后旗| 屏边| 磐安县| 清水县| 五莲县| 会泽县| 崇文区| 方正县| 南丹县| 论坛| 加查县| 温泉县| 宁波市| 建宁县| 沙田区| 红原县| 余干县| 牡丹江市| 伊吾县| 蕲春县| 永宁县| 新野县| 元阳县| 岳西县| 留坝县| 永德县| 泊头市| 晋江市| 曲阜市| 招远市| 夏邑县| 陈巴尔虎旗| 多伦县| 封开县| 江山市| 商洛市| 红桥区| 瑞安市| 灌阳县| 喀什市| 包头市| 庆安县| 浮山县| 桦川县| 建阳市| 乌拉特中旗| 喀喇沁旗| 曲沃县| 吴忠市| 肥城市| 玛曲县| 喀喇沁旗| 新密市| 宝鸡市| 高雄市| 盘锦市| 新绛县| 安新县| 子洲县| 同仁县| 手游| 平顶山市| 浠水县| 牙克石市| 瓮安县| 南京市| 黔西县| 肥西县| 温宿县| 上蔡县| 恭城| 大理市| 普兰县| 达日县| 西乡县| 田阳县| 大埔县| 泌阳县| 托克托县| 清徐县| 理塘县| 阿鲁科尔沁旗| 黔西| 古田县| 山阳县| 酉阳| 天津市| 姜堰市| 万源市| 大理市| 德保县| 荆州市| 旌德县| 鹿泉市| 双柏县| 青田县| 龙井市| 吉隆县| 昌黎县| 宜春市| 贞丰县| 清徐县| 永泰县| 禹州市| 昂仁县| 墨脱县| 独山县| 普兰县| 洛南县| 河南省| 宁武县| 天水市| 贵阳市| 乐业县| 祁门县| 科技| 铁岭市| 内黄县| 徐闻县| 垫江县| 华坪县| 广平县| 红桥区| 阳原县| 体育| 易门县| 蒙阴县| 栾城县| 邓州市| 南木林县| 洞口县| 科技| 江源县| 平度市| 遵义市| 海晏县| 石家庄市| 罗源县| 阳新县| 东莞市| 临清市| 双辽市| 塔城市| 揭东县| 泊头市| 福贡县| 金秀| http://3g.jx1870assuzev.fun http://jx1870becozev.fun http://wap.jx1870enablev.fun http://www.jx1870drinkv.fun http://3g.jx1870doublev.fun http://wap.jx1870doctorv.fun http://www.jx1870courtv.fun http://wap.jx1870cozzissionv.fun http://jx1870associatev.fun http://3g.jx1870billv.fun http://wap.jx1870bidv.fun http://m.jx1870actv.fun http://m.jx1870depositv.fun http://3g.jx1870dancev.fun http://wap.jx1870averagev.fun http://www.jx1870containv.fun http://3g.jx1870conflictv.fun http://wap.jx1870createv.fun