<menu id="gc4q0"></menu>
  • <menu id="gc4q0"></menu>
  • <input id="gc4q0"></input>
    <nav id="gc4q0"></nav>
  • <input id="gc4q0"><acronym id="gc4q0"></acronym></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>了……

    相关文章
    相关标签/搜索
    香港最快現场开奖结果118图库天下彩天空彩免费大全香港蓝月亮精选资料六合宝典天天彩票新版 南召县| 榆中县| 北海市| 柳河县| 盐山县| 石狮市| 多伦县| 九江县| 抚顺市| 绥阳县| 麻城市| 宁远县| 宣城市| 房山区| 江门市| 军事| 化隆| 紫金县| 定日县| 通州市| 乳山市| 漠河县| 娄烦县| 亚东县| 奉贤区| 荥经县| 栾城县| 连平县| 托克逊县| 虎林市| 苍梧县| 永顺县| 云林县| 海城市| 瑞昌市| 桂平市| 临澧县| 濮阳县| 保亭| 石家庄市| 江孜县| 鸡西市| 三原县| 商城县| 中西区| 昆山市| 东安县| 沙洋县| 大方县| 凯里市| 濮阳市| 宁津县| 鞍山市| 河北省| 淳化县| 平度市| 手游| 伊金霍洛旗| 乌什县| 海城市| 宁乡县| SHOW| 甘肃省| 鄯善县| 汾阳市| 石柱| 灵宝市| 锡林郭勒盟| 乌兰浩特市| 买车| 南漳县| 股票| 吐鲁番市| 尤溪县| 株洲县| 长武县| 陵川县| 昌乐县| 双桥区| 彭阳县| 萨迦县| 浦北县| 武鸣县| 乐清市| 西宁市| 长武县| 云阳县| 永新县| 南开区| 横峰县| 邢台市| 嵊泗县| 拉孜县| 海淀区| 凌海市| 英超| 贺兰县| 藁城市| 泾源县| 郸城县| 龙胜| 安吉县| 璧山县| 惠安县| 通州区| 昌邑市| 区。| 江津市| 绥中县| 永康市| 开平市| 民县| 英超| 高州市| 台州市| 新营市| 文登市| 皮山县| 黔江区| 额敏县| 华蓥市| 武安市| 始兴县| 关岭| 蓝田县| 务川| 西乡县| 宝鸡市| 舞阳县| 河津市| 澳门| 高台县| 南漳县| 阿克| 肇源县| 保山市| 枣强县| 方山县| 桦甸市| 广灵县| 鄂托克前旗| 南平市| 丰台区| 谢通门县| 淮滨县| 南丰县| 五原县| 当雄县| 济源市| 紫阳县| 昌邑市| 石嘴山市| 嘉兴市| 滨州市| 辰溪县| 九寨沟县| 灵武市| 西林县| 平度市| 乌兰浩特市| 达拉特旗| 敦煌市| 三门峡市| 墨江| 敖汉旗| 青铜峡市| 西藏| 永济市| 醴陵市| 宁南县| 高清| 手游| 太保市| 任丘市| 晋城| 南部县| 汝阳县| 泰来县| 安多县| 安阳县| 元朗区| 定远县| 宣恩县| 海口市| 吴旗县| 加查县| 洛浦县| 湟中县| 武威市| 五华县| 福建省| 哈尔滨市| 西青区| 金阳县| 双辽市| 苍梧县| 图木舒克市| 西宁市| 永定县| 汉中市| 西宁市| 桃园县| 应用必备| 寿宁县| 宁国市| 博爱县| 合肥市| 宣武区| 荆门市| 海安县| 邮箱| 都昌县| 札达县| 金乡县| 庄浪县| 鄂伦春自治旗| 阳朔县| 永胜县| 吴忠市| 玉屏| 拉孜县| 梓潼县| 鄱阳县| 新昌县| 富宁县| 永泰县| 新竹市| 深圳市| 河西区| 平凉市| 普陀区| 郧西县| 巴青县| 新宾| 灵武市| 镇宁| 龙州县| 孟津县| 绥滨县| 灵寿县| 马龙县| 本溪市| 深水埗区| 元阳县| 临沭县| 乌鲁木齐市| 衡山县| 营山县| 新绛县| 昌邑市| 广州市| 昭觉县| 博罗县| 海伦市| 迁安市| 淮阳县| 磴口县| 福贡县| 济南市| 高台县| 兴宁市| 吕梁市| 惠安县| 肥西县| 邵武市| 修水县| 千阳县| 囊谦县| 肥乡县| 囊谦县| 隆子县| 桐柏县| 柳林县| 蒲城县| 蓬莱市| 新巴尔虎左旗| 离岛区| 潮州市| 阿勒泰市| 浦城县| 宣恩县| 三门峡市| 巴塘县| 江川县| 屯昌县| 当阳市| 开原市| 襄垣县| 久治县| 蓬安县| 南陵县| 定边县| 阜南县| 迁西县| 荔浦县| SHOW| 原阳县| 邵阳市| 儋州市| 和政县| 牡丹江市| 鱼台县| 聊城市| 河西区| 黔西| 吴川市| 灌南县| 南木林县| 青岛市| 韩城市| 山西省| 平度市| 长宁县| 华池县| 罗甸县| 和田县| 且末县| 华池县| 松潘县| 南阳市| 林甸县| 石林| 德化县| 巴东县| 金寨县| 丹棱县| 锡林浩特市| 昭平县| http://3g.bo2020views.fun http://3g.gz1980deliverc.fun http://3g.yqo3j0rl8v.fun http://3g.bo2020represents.fun http://3g.bo2020regards.fun http://3g.bo2020contrasts.fun http://3g.gz1980scalec.fun http://3g.yqo9j6rl8v.fun http://3g.bo2020walls.fun http://3g.bo2020cozes.fun http://3g.gz1980conflictc.fun http://3g.yqo5j3rl7v.fun http://3g.bo2020cycles.fun http://3g.gz1980cottonc.fun http://3g.yqo5j0rl5v.fun http://3g.bo2020functions.fun http://3g.gz1980replyc.fun http://3g.yqo4j0rl7v.fun