<sub id="fhvtr"></sub><sub id="fhvtr"></sub>

      <address id="fhvtr"></address>

              <sub id="fhvtr"></sub>

                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年香港六合马会开奖结果现场直播开奖历史资料记录在线查询网 花莲市| 开平市| 城固县| 明水县| 仙桃市| 西平县| 紫阳县| 阳朔县| 资源县| 南涧| 隆昌县| 宁晋县| 苏尼特右旗| 巴楚县| 嘉善县| 普格县| 澎湖县| 克什克腾旗| 广汉市| 兴城市| 固阳县| 应用必备| 清流县| 大安市| 日土县| 宁海县| 大埔区| 砀山县| 沙湾县| 扬州市| 邻水| 安达市| 荣昌县| 凭祥市| 东乌珠穆沁旗| 天水市| 林芝县| 贵港市| 定州市| 凯里市| 包头市| 大英县| 湘西| 佛山市| 江口县| 军事| 新邵县| 沙洋县| 丰顺县| 津市市| 东平县| 恩施市| 彭州市| 微山县| 乐安县| 通辽市| 夏津县| 家居| 华容县| 安多县| 勃利县| 祥云县| 济阳县| 佛山市| 佛山市| 延津县| 施秉县| 思茅市| 普定县| 宝兴县| 延津县| 乌什县| 罗田县| 会理县| 乌鲁木齐市| 天峨县| 紫云| 达孜县| 山西省| 金寨县| 林州市| 兖州市| 桂林市| 建水县| 长顺县| 台州市| 格尔木市| 中阳县| 攀枝花市| 新竹市| 通许县| 文山县| 深泽县| 洞头县| 隆德县| 延津县| 钦州市| 屏东县| 犍为县| 甘孜县| 瑞金市| 双城市| 伊宁市| 上犹县| 玛曲县| 东阿县| 崇州市| 连山| 昌吉市| 启东市| 绥宁县| 宁夏| 清流县| 富宁县| 黑龙江省| 昌都县| 广安市| 民县| 泸州市| 余干县| 广西| 习水县| 清水河县| 五原县| 济南市| 万州区| 五指山市| 北辰区| 唐海县| 青冈县| 晋江市| 敦化市| 怀远县| 磐石市| 黎城县| 马关县| 安远县| 湘乡市| 大兴区| 鹤岗市| 栖霞市| 德保县| 雷山县| 措美县| 潞西市| 高州市| 天台县| 河东区| 新兴县| 抚远县| 平凉市| 孟州市| 屯留县| 内江市| 土默特左旗| 乐东| 延川县| 康保县| 昔阳县| 新乐市| 深州市| 依安县| 白山市| 乌兰浩特市| 浦东新区| 伽师县| 达日县| 江安县| 宜昌市| 突泉县| 胶南市| 泸西县| 鄂伦春自治旗| 乐至县| 广平县| 荆州市| 天峻县| 柏乡县| 东乌珠穆沁旗| 万年县| 县级市| 西城区| 新疆| 泰州市| 平定县| 基隆市| 卫辉市| 华安县| 昌吉市| 利川市| 观塘区| 拉萨市| 杨浦区| 高州市| 达孜县| 白沙| 长沙县| 东安县| 镇平县| 华阴市| 广元市| 柘城县| 崇义县| 民勤县| 星子县| 西和县| 郎溪县| 府谷县| 怀仁县| 珠海市| 定兴县| 西华县| 铜梁县| 东乡族自治县| 顺义区| 张北县| 和硕县| 屯门区| 思茅市| 临泉县| 文化| 始兴县| 阳高县| 钟山县| 鸡西市| 个旧市| 台前县| 岐山县| 横峰县| 昭平县| 班玛县| 河东区| 锡林浩特市| 南川市| 习水县| 犍为县| 浦县| 孟州市| 阜南县| 华安县| 上高县| 吴江市| 喜德县| 句容市| 蒙山县| 长阳| 广河县| 抚松县| 莲花县| 安仁县| 南溪县| 西乡县| 金沙县| 老河口市| 内丘县| 淮安市| 屏南县| 盖州市| 鄂温| 游戏| 吉水县| 尼木县| 金秀| 达日县| 黔西县| 东乡族自治县| 彭泽县| 怀化市| 德阳市| 花莲县| 观塘区| 永川市| 沂南县| 双城市| 桃园市| 大余县| 安宁市| 福安市| 墨玉县| 德清县| 增城市| 定边县| 乌鲁木齐县| 丰顺县| 宜良县| 个旧市| 炎陵县| 夏邑县| 肥城市| 海城市| 聂拉木县| 许昌县| 吉林省| 乌恰县| 定陶县| 丰原市| 浦北县| 漾濞| 武威市| 安新县| 高碑店市| 武邑县| 乌恰县| 台东县| 台北市| 青铜峡市| 旬邑县| 武定县| 成武县| 绥滨县| 南投市| 双柏县| 兴国县| 峨山| 翼城县| 安福县| 昆明市| 收藏| 富川| 新竹市| 阿克陶县| 木里| 资阳市| 遂宁市| 儋州市| 阳新县| 瓦房店市| 江川县| 将乐县| 恭城| 瓦房店市| 兴文县| 宁陕县| 清苑县| 沾化县| 开阳县| 罗甸县| 贡山| 延川县| 昌吉市| 通海县| 鹤壁市| 浦江县| 宁夏| 民和| 刚察县| 淮南市| 梧州市| 陵川县| 衡山县| 奎屯市| 乌拉特后旗| 砚山县| 尼勒克县| 澎湖县| 吕梁市| 伊金霍洛旗| 湘阴县| 邓州市| 齐齐哈尔市| 建昌县| 孟连| 平和县| 甘谷县| 南安市| 玛曲县| 绩溪县| 仲巴县| 花垣县| 舟曲县| 上饶市| 开阳县| 宜良县| 稻城县| 清镇市| 桂平市| 延长县| 西充县| 婺源县| 赤城县| 大荔县| 新野县| 道真| 沂南县| 凌海市| 岳阳市| 陇西县| 新营市| 额尔古纳市| 云南省| 泾阳县| 凤翔县| 昌吉市| 奎屯市| 临夏市| 峨眉山市| 汝南县| 虹口区| 宣武区| 巴塘县| 内黄县| 娄烦县| 丰顺县| 内丘县| 利川市| 普兰店市| 嘉善县| 长葛市| 县级市| 克拉玛依市| 三明市| 潍坊市| 荥阳市| 丹凤县| 雷波县| 新邵县| 肥西县| 淳化县| 汶上县| 宁晋县| 多伦县| 云浮市| 临夏市| 辽阳市| 朝阳市| 东安县| 隆安县| 疏勒县| 滦南县| 静海县| 承德市| 视频| 泽库县| 万山特区| 长岛县| 鄂伦春自治旗| 安国市| 苍溪县| 方正县| 长武县| 和林格尔县| 阳西县| 昌江| 肃北| 永吉县| 兰溪市| 泉州市| 内黄县| 四会市| 阳朔县| 惠州市| 溆浦县| 罗山县| 抚远县| 收藏| 建始县| 阿拉善左旗| 五峰| 蛟河市| 德江县| 黎城县| 项城市| 揭阳市| 榆林市| 武清区| 肇东市| 阜南县| 阿拉善左旗| 庐江县| 仪征市| 广饶县| 北安市| 阜新| 微山县| 四子王旗| 重庆市| 获嘉县| 台东市| 云和县| 蒲江县| 文水县| 化州市| 秦皇岛市| 三门县| 天等县| 金沙县| 靖西县| 齐河县| 龙海市| 榆社县| 陕西省| 四会市| 阳高县| 县级市| 桂阳县| 五原县| 岳池县| 南平市| 仁布县| 吉林省| 常德市| 西吉县| 西丰县| 大田县| 垦利县| 平顶山市| 博白县| 上饶市| 兴安盟| 西贡区| 恩平市| 修水县| 保德县| 新邵县| 基隆市| 莆田市| 海兴县| 平顶山市| 清涧县| 河源市| 上饶市| 天门市| 台中市| 四子王旗| 同江市| 阿拉善右旗| 通城县| 青浦区| 秦皇岛市| 南投市| 永靖县| 丹江口市| 德清县| 北川| 泗阳县| 巴青县| 呼和浩特市| 彝良县| 福鼎市| 平果县| 建平县| 东山县| 金山区| 乐清市| 怀远县| 枣强县| 凤翔县| 彭山县| 东阳市| 永胜县| 遂川县| 扶风县| 樟树市| 江安县| 徐水县| 诸暨市| 西充县| 河间市| 滁州市| 普兰店市| 东源县| 九龙坡区| 涪陵区| 肥东县| 游戏| 台东市| 雅江县| 无为县| 赤峰市| 日土县| 株洲市| 密山市| 若尔盖县| 兴和县| 万安县| 堆龙德庆县| 泰和县| 施秉县| 嘉黎县| 宽甸| 长顺县| 定安县| 瑞丽市| 遵义县| 怀集县| 溆浦县| 枞阳县| 阿合奇县| 大理市| 崇仁县| 乐都县| 高安市| 云南省| 扎赉特旗| 宜宾县| 海林市| 普宁市| 新源县| 额尔古纳市| 海阳市| 老河口市| 资阳市| 九龙县| 蕲春县| 宁波市| 探索| 阳山县| 舟山市| 鞍山市| 航空| 栖霞市| 商南县| 洛阳市| 特克斯县| 瑞昌市| http://bm1961xindz.fit http://m.thdbwo.fit http://wap.ukgugn.fit http://m.pevlpu.fit http://www.lfdlnb.fit http://wap.pnqysh.fit http://www.sgvqdh.fit http://wap.dmhhki.fit http://m.huvjhh.fit http://bm1961xassz.fit http://m.keisog.fit http://www.zyvhqo.fit http://wap.cejzxv.fit http://bnsptt.fit http://m.fsmlea.fit http://www.psvpen.fit http://wap.bm1961notez.fit http://mxzxdv.fit