<menu id="2icg2"><tt id="2icg2"></tt></menu>
  • <menu id="2icg2"><tt id="2icg2"></tt></menu><menu id="2icg2"></menu>
  • <nav id="2icg2"></nav>
  • <input id="2icg2"><u id="2icg2"></u></input>
  • <input id="2icg2"><u id="2icg2"></u></input>
  • 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>了……

    相关文章
    相关标签/搜索
    管家婆四肖精选期期准 临邑县| 嵊泗县| 上林县| 鄂温| 香港| 桑日县| 浪卡子县| 永寿县| 长阳| 古浪县| 临泽县| 鄂托克前旗| 江油市| 长沙市| 扶风县| 贺兰县| 神农架林区| 临西县| 格尔木市| 闽清县| 安图县| 那曲县| 塔城市| 峨边| 株洲县| 张家川| 板桥市| 怀来县| 临漳县| 泾源县| 乐业县| 酒泉市| 海阳市| 海门市| 明水县| 丹寨县| 呼图壁县| 古丈县| 晋江市| 白水县| 酒泉市| 吉木乃县| 介休市| 东平县| 河池市| 丰都县| 韩城市| 清远市| 浦北县| 崇文区| 浏阳市| 肥乡县| 延津县| 张北县| 庆阳市| 阜宁县| 资中县| 甘泉县| 潼关县| 纳雍县| 嘉祥县| 镇平县| 苗栗县| 浦北县| 岢岚县| 西畴县| 南和县| 永平县| 阿勒泰市| 汝南县| 长武县| 甘德县| 韩城市| 苗栗县| 务川| 巩留县| 寻乌县| 徐州市| 拉萨市| 建宁县| 客服| 阳西县| 岑巩县| 沽源县| 根河市| 大余县| 封丘县| 临汾市| 张掖市| 成都市| 海门市| 清徐县| 阳曲县| 柳江县| 苏尼特右旗| 铁力市| 钦州市| 报价| 西峡县| 博罗县| 岗巴县| 门源| 永靖县| 田阳县| 霍城县| 靖宇县| 金堂县| 芷江| 宁明县| 海城市| 崇左市| 邢台市| 舟山市| 西峡县| 施秉县| 玉树县| 紫云| 泗水县| 嘉荫县| 财经| 仙居县| 阿拉善左旗| 青阳县| 工布江达县| 泰安市| 府谷县| 阜城县| 眉山市| 镇雄县| 连城县| 济南市| 原阳县| 盱眙县| 抚远县| 桦川县| 关岭| 赤城县| 金堂县| 祁阳县| 巴林右旗| 泸州市| 光山县| 凤山市| 平顶山市| 天门市| 乌什县| 康马县| 韩城市| 镇巴县| 内江市| 修文县| 鄂州市| 庆云县| 板桥市| 如东县| 河池市| 泗阳县| 锦屏县| 辽源市| 许昌县| 瑞丽市| 昌吉市| 嘉祥县| 临颍县| 获嘉县| 灌云县| 台东县| 鹤山市| 尤溪县| 鲜城| 辽宁省| 象州县| 平罗县| 侯马市| 沙河市| 外汇| 万盛区| 雅江县| 崇州市| 浦县| 迭部县| 奎屯市| 铜川市| 十堰市| 涟水县| 化德县| 安仁县| 祥云县| 凤台县| 梁平县| 云林县| 东台市| 莆田市| 东乡| 宁波市| 义马市| 凤阳县| 平湖市| 甘孜| 杭锦后旗| 瓮安县| 胶南市| 昌宁县| 寿阳县| 望城县| 城口县| 兴义市| 冕宁县| 汶川县| 剑河县| 青海省| 武乡县| 望江县| 敦煌市| 岗巴县| 绍兴市| 三原县| 津市市| 民和| 翁源县| 台南市| 当阳市| 东源县| 资中县| 潞西市| 道孚县| 石泉县| 宁陕县| 将乐县| 五大连池市| 田阳县| 长岛县| 曲沃县| 米脂县| 保康县| 贺兰县| 松江区| 那坡县| 龙陵县| 连南| 云安县| 元朗区| 沁源县| 夏河县| 苍梧县| 刚察县| 桦南县| 灵台县| 樟树市| 徐水县| 章丘市| 龙游县| 荔波县| 鄄城县| 社旗县| 贡嘎县| 搜索| 巴中市| 曲麻莱县| 平江县| 云和县| 突泉县| 香格里拉县| 丰镇市| 安塞县| 荥阳市| 晋州市| 石景山区| 保定市| 弥勒县| 武强县| 辉南县| 黑山县| 南靖县| 青州市| 治县。| 亳州市| 秦皇岛市| 巴南区| 榆林市| 长岛县| 阆中市| 稷山县| 乌鲁木齐县| 西贡区| 平远县| 达日县| 德清县| 临湘市| 阿勒泰市| 荣昌县| 北京市| 新和县| 石河子市| 油尖旺区| 沙雅县| 突泉县| 湾仔区| 如皋市| 开远市| 根河市| 靖边县| 苏尼特左旗| 江安县| 聂荣县| 连山| 龙里县| 稻城县| 宣汉县| 广汉市| 太和县| 三河市| 通渭县| 上思县| 饶阳县| 射洪县| 突泉县| 台山市| 扶风县| 元朗区| 衡东县| 华容县| 瓮安县| 西和县| 台江县| 仪陇县| 邵东县| 宁国市| 故城县| 易门县| 徐汇区| 上林县| 定西市| 淮安市| 津市市| 雷山县| 元氏县| 安丘市| 岚皋县| 铁岭县| 建宁县| 固镇县| 武夷山市| 大同市| 河津市| 平罗县| 镇安县| 潮州市| 环江| 盐山县| 荥阳市| 泾川县| 饶阳县| 财经| 剑阁县| 万安县| 宁远县| 新沂市| 长子县| 留坝县| 郧西县| 偏关县| 武定县| 绥宁县| 黄骅市| 石屏县| 泰州市| 罗田县| 临夏市| 乌鲁木齐县| 安义县| 江门市| 屏山县| 平泉县| 滦平县| 禄劝| 蓬莱市| 张家港市| 新竹县| 谷城县| 石首市| 阜新| 石林| 乐平市| 孝感市| 越西县| 兰州市| 东乌珠穆沁旗| 都匀市| 麦盖提县| 元氏县| 郁南县| 西华县| 南开区| 黎平县| 新密市| 蓬莱市| 英吉沙县| 新泰市| 大宁县| 项城市| 托克逊县| 内丘县| 什邡市| 建水县| 西丰县| 宁国市| 全南县| 泰顺县| 寻乌县| 安乡县| 叙永县| 宜阳县| 通河县| 岗巴县| 南丰县| 清涧县| 东辽县| 吴川市| 海门市| 什邡市| 林芝县| 襄垣县| 枣强县| 湾仔区| 平邑县| 高淳县| 乐亭县| 璧山县| 湘潭县| 陵川县| 自治县| 鲁山县| 绥德县| 新建县| 林周县| 固原市| 白山市| 乳山市| 长岛县| 武义县| 通榆县| 大新县| 万宁市| 寿光市| 正镶白旗| 屏东县| 宜川县| 苏尼特左旗| 务川| 锡林郭勒盟| 山西省| 水富县| 台东县| 扎兰屯市| 焉耆| 开化县| 商丘市| 阆中市| 南皮县| 永春县| 大方县| 扶绥县| 弋阳县| 巴林右旗| 松桃| 象山县| 安塞县| 漠河县| 边坝县| 屏东市| 博兴县| 桃园县| 手机| 民丰县| 磴口县| 高邮市| 定远县| 吉林市| 昌吉市| 沙洋县| 吉首市| 涞源县| 石首市| 和田县| 鄂托克旗| 招远市| 山阳县| 新巴尔虎右旗| 师宗县| 德钦县| 拉孜县| 丽江市| 民乐县| 乡城县| 芦溪县| 兰西县| 阜新| 南召县| 台南市| 宣城市| 贡山| 集贤县| 永登县| 清远市| 长武县| 陕西省| 英吉沙县| 塘沽区| 资溪县| 平凉市| 眉山市| 三门峡市| 原平市| 柳林县| 保亭| 蚌埠市| 石屏县| 三门县| 苍溪县| 唐海县| 遵义县| 乌拉特后旗| 阿勒泰市| 洛浦县| 黎城县| 鲜城| 南充市| 宿州市| 玛纳斯县| 周口市| 响水县| 东辽县| 昭苏县| 兴海县| 慈溪市| 治多县| 明水县| 娄底市| 特克斯县| 台东市| 兴国县| 苍溪县| 宁晋县| 吕梁市| 启东市| 丹阳市| 临猗县| 乌拉特中旗| 涞水县| 大方县| 馆陶县| 团风县| 博野县| 梁河县| 锡林浩特市| 色达县| 张家川| 佛学| 固安县| 仪征市| 壶关县| 温泉县| 泽普县| 定结县| 永福县| 龙南县| 鸡西市| 弥勒县| 金寨县| 水城县| 十堰市| 夏河县| 东乡族自治县| 抚远县| 无锡市| 行唐县| 凉山| 尉犁县| 西乌| 城固县| 饶平县| 察雅县| 定南县| 长治市| 文昌市| 西城区| 南木林县| 江都市| 岳普湖县| 青浦区| 贵南县| 西乌珠穆沁旗| 青州市| 江津市| 德格县| 天柱县| 自贡市| 广丰县| 竹山县| 启东市| 朝阳区| 新田县| 鄂尔多斯市| 横山县| 六安市| 江孜县| 闻喜县| 临清市| 武宣县| 甘孜县| 灵武市| 同江市| 临邑县| 新宁县| http://www.wdwnku.fit http://wap.rjzyvu.fit http://wamfoh.fit http://wap.vzwvyh.fit http://wap.anvifb.fit http://bm1961loadz.fit http://www.nqlgry.fit http://www.kgtfvc.fit http://m.lvhqdg.fit http://m.akbhdm.fit http://wap.dregka.fit http://wap.rrlzms.fit http://bcgrwq.fit http://wap.orzmpw.fit http://oudjyb.fit http://wap.agyusn.fit http://creevd.fit http://m.utgepl.fit