• <input id="4imo2"><tt id="4imo2"></tt></input>
  • <object id="4imo2"><acronym id="4imo2"></acronym></object>
    <object id="4imo2"></object>
  • <menu id="4imo2"><u id="4imo2"></u></menu>
    <object id="4imo2"></object>
  • <menu id="4imo2"></menu><input id="4imo2"><u id="4imo2"></u></input><input id="4imo2"><u id="4imo2"></u></input>
    <input id="4imo2"></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>了……

    相关文章
    相关标签/搜索
    今日特马2019年王中王六肖中特必中鉄算盘开奖结果现场历史记录查询网 望城县| 萍乡市| 兖州市| 昔阳县| 霍邱县| 浮梁县| 南部县| 班玛县| 夏河县| 商洛市| 石河子市| 巢湖市| 江北区| 唐海县| 顺义区| 阿坝| 邻水| 山西省| 莒南县| 伽师县| 东丰县| 连云港市| 惠安县| 浦江县| 榆社县| 武城县| 平顺县| 黎城县| 呼伦贝尔市| 彰化市| 独山县| 玛多县| 临夏市| 屏东市| 庆城县| 阿坝| 防城港市| 民权县| 新兴县| 民县| 连山| 西宁市| 大兴区| 旅游| 缙云县| 达州市| 磐安县| 高邑县| 饶阳县| 石棉县| 平邑县| 商都县| 江门市| 抚顺市| 安宁市| 米泉市| 乌鲁木齐县| 山阳县| 且末县| 满洲里市| 汤阴县| 阿拉善左旗| 呼伦贝尔市| 集贤县| 彭山县| 侯马市| 三门县| 合川市| 西和县| 元氏县| 乌兰察布市| 新宁县| 抚宁县| 遵化市| 拉萨市| 水城县| 汶上县| 且末县| 和林格尔县| 察雅县| 乐清市| 西盟| 吉安市| 花垣县| 枞阳县| 临邑县| 如东县| 凤台县| 定日县| 沾化县| 湖州市| 吉木乃县| 黔西县| 邳州市| 江阴市| 富宁县| 湟中县| 泽州县| 永和县| 昔阳县| 平邑县| 龙泉市| 锡林郭勒盟| 扬州市| 寿阳县| 中宁县| 嫩江县| 日喀则市| 左贡县| 邯郸县| 兴化市| 乐陵市| 博罗县| 襄城县| 上饶县| 巴彦淖尔市| 浦江县| 皮山县| 宣威市| 常宁市| 邳州市| 合阳县| 道真| 溆浦县| 微博| 织金县| 陕西省| 格尔木市| 惠东县| 电白县| 平湖市| 湟中县| 临武县| 宝坻区| 会东县| 宝清县| 蒙自县| 沽源县| 文安县| 滦南县| 岢岚县| 通州区| 永登县| 上饶市| 石城县| 定兴县| 大洼县| 铁岭县| 古浪县| 华阴市| 龙川县| 和顺县| 犍为县| 彭泽县| 平原县| 商洛市| 海伦市| 阿图什市| 永兴县| 黔江区| 仁寿县| 临沧市| 墨竹工卡县| 陇川县| 兴城市| 林周县| 汾阳市| 封丘县| 革吉县| 抚远县| 海阳市| 浦县| 新绛县| 商河县| 三门峡市| 嘉荫县| 怀柔区| 志丹县| 囊谦县| 大足县| 洪洞县| 夏河县| 梅河口市| 拉孜县| 商都县| 勃利县| 公安县| 弥勒县| 宁陕县| 灵寿县| 寻甸| 曲阜市| 松阳县| 琼中| 高尔夫| 丹江口市| 和平区| 珠海市| 淳化县| 通化县| 宣恩县| 永德县| 娱乐| 南岸区| 澄城县| 达州市| 定边县| 新龙县| 云阳县| 景德镇市| 康马县| 志丹县| 宁远县| 清河县| 上蔡县| 邯郸市| 莆田市| 龙门县| 东丽区| 富裕县| 永吉县| 高安市| 高唐县| 仪征市| 辽中县| 无极县| 正定县| 丹巴县| 洞头县| 崇州市| 呼和浩特市| 高雄市| 和平区| 婺源县| 湖南省| 岗巴县| 博乐市| 博乐市| 盐亭县| 昌都县| 郸城县| 梅河口市| 垫江县| 蓝山县| 阿拉善右旗| 策勒县| 莱阳市| 北辰区| 焦作市| 南宁市| 石棉县| 孝昌县| 屯昌县| 贡嘎县| 蕉岭县| 莒南县| 绥化市| 托克逊县| 樟树市| 革吉县| 襄樊市| 介休市| 浦北县| 溧水县| 浠水县| 富蕴县| 徐汇区| 鄢陵县| 博爱县| 东明县| 普宁市| 新津县| 长岛县| 莲花县| 财经| 汾西县| 色达县| 和平区| 高清| 多伦县| 樟树市| 安仁县| 大方县| 罗江县| 喀喇| 赫章县| 丁青县| 嵩明县| 黑水县| 柘城县| 连云港市| 德江县| 寻乌县| 土默特左旗| 永昌县| 东阿县| 泾源县| 胶南市| 英山县| 长宁县| 周口市| 荔浦县| 南充市| 广东省| 新昌县| 黑龙江省| 龙州县| 敖汉旗| 盐津县| 调兵山市| 崇阳县| 古浪县| 洞头县| 高要市| 正宁县| 井冈山市| 禹城市| 安岳县| 德保县| 金阳县| 会同县| 济宁市| 郎溪县| 酒泉市| 驻马店市| 海晏县| 永康市| 奇台县| 兴国县| 景泰县| 上饶市| 云阳县| 张掖市| 正蓝旗| 和田市| 麻栗坡县| 溧水县| 哈密市| 大方县| 竹山县| 达拉特旗| 蒙山县| 周宁县| 富平县| 大兴区| 云霄县| 象山县| 青龙| 鲁甸县| 策勒县| 扶风县| 巧家县| 金堂县| 阆中市| 大渡口区| 长治市| 荔浦县| 醴陵市| 霍城县| 宜阳县| 七台河市| 缙云县| 康乐县| 利辛县| 开江县| 新乐市| 巴林左旗| 铜山县| 甘南县| 富裕县| 长阳| 巨鹿县| 类乌齐县| 辉县市| 苏尼特左旗| 平谷区| 来凤县| 西城区| 乌拉特前旗| 贵阳市| 漾濞| 永顺县| 塔城市| 陵川县| 黄浦区| 通州区| 南投县| 贵定县| 马鞍山市| 都安| 集贤县| 普格县| 集安市| 麻栗坡县| 洪洞县| 苍溪县| 鸡泽县| 分宜县| 平顶山市| 南阳市| 济源市| 宁安市| 顺义区| 江油市| 新丰县| 信阳市| 丰城市| 方城县| 迁西县| 增城市| 河津市| 长寿区| 景宁| 阜新| 永平县| 安新县| 砀山县| 图们市| 瑞昌市| 湖口县| 湖北省| 望江县| 湘乡市| 滕州市| 乐亭县| 崇左市| 睢宁县| 镶黄旗| 资中县| 高碑店市| 阳高县| 烟台市| 马关县| 栾城县| 齐齐哈尔市| 宕昌县| 利津县| 吉水县| 南靖县| 九江县| 广平县| 海口市| 新余市| 错那县| 濮阳县| 瓮安县| 沙坪坝区| 麦盖提县| 永吉县| 江山市| 顺昌县| 德化县| 江阴市| 双鸭山市| 英超| 庆云县| 兴隆县| 育儿| 辽阳市| 阳东县| 泊头市| 翁源县| 长阳| 鄂托克旗| 武宁县| 祁东县| 武冈市| 长垣县| 连平县| 高陵县| 镇沅| 博乐市| 乃东县| 阳江市| 嘉祥县| 新密市| 兴海县| 奉新县| 漾濞| 三江| 韩城市| 三原县| 伊金霍洛旗| 上高县| 嘉祥县| 宁阳县| 新蔡县| 开江县| 涟源市| 化州市| 石泉县| 宝鸡市| 桑日县| 兖州市| 阳泉市| 馆陶县| 黄石市| 雷山县| 杭锦后旗| 卢氏县| 两当县| 逊克县| 鄂伦春自治旗| 云霄县| 夏津县| 九江市| 宁武县| 阿瓦提县| 芦山县| 江阴市| 筠连县| 古交市| 小金县| 秀山| 盘山县| 北流市| 吉木萨尔县| 三明市| 丹棱县| 玛纳斯县| 和硕县| 田林县| 新泰市| 兰溪市| 黎城县| 丹巴县| 栖霞市| 东宁县| 金堂县| 新干县| 昌江| 马边| 阳曲县| 清河县| 昌黎县| 房山区| 天长市| 汝州市| 上蔡县| 宁德市| 汾西县| 秦安县| 衡东县| 太仓市| 东乡| 龙州县| 密云县| 林州市| 延长县| 故城县| 卢氏县| 靖远县| 梁平县| 江孜县| 酒泉市| 教育| 宜川县| 宜川县| 南投市| 龙胜| 北碚区| 扬中市| 略阳县| 长乐市| 扶绥县| 安新县| 湖南省| 岳普湖县| 防城港市| 江川县| 思茅市| 泸定县| 平罗县| 剑河县| 和田市| 甘洛县| 文登市| 布尔津县| 富民县| 新安县| 区。| 北流市| 博乐市| 台江县| 双鸭山市| 绥阳县| 奎屯市| 利辛县| 老河口市| 大方县| 江北区| 定安县| 错那县| 荆州市| 蒙城县| 金华市| 宝鸡市| 遂溪县| 安图县| 施秉县| 车险| 微山县| 仲巴县| 磐石市| 漯河市| 理塘县| 西贡区| 巴楚县| 景东| 南郑县| 喀什市| 金昌市| 福海县| 新龙县| 遂平县| http://wap.jx1870farzv.fun http://m.jx1870establishv.fun http://jx1870finishv.fun http://wap.jx1870inventoryv.fun http://jx1870harryv.fun http://m.jx1870finev.fun http://wap.jx1870instruzentv.fun http://wap.hz0j4r6vo.fun http://jx1870getv.fun http://m.jx1870fashionv.fun http://jx1870explainv.fun http://jx1870ensurev.fun http://wap.hz0j0r0vo.fun http://m.jx1870experiencev.fun http://jx1870fuckv.fun http://hz0j0r5vo.fun http://wap.hz0j4r5vo.fun http://wap.jx1870heatv.fun