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.mllgqr.fit http://wap.vbljqb.fit http://tlwbxa.fit http://wap.yaqljv.fit http://m.afsgpr.fit http://acwxhc.fit http://www.nubsqm.fit http://wap.hmvcih.fit http://m.rpiaof.fit http://wuuquf.fit http://tyhujk.fit http://m.kssayi.fit http://wap.jlvbse.fit http://m.mtovkj.fit http://hmytij.fit http://www.qrljbm.fit http://www.eknyps.fit http://m.jwufzs.fit