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>了……

          相关文章
          相关标签/搜索
          三十码期期必中√资料今晚六给彩开奖结果,白小姐中特玄机,六开彩开奖现场直播,2017开奖记录开奖结果,开马现场直播,马报免费资料2017大全 柞水县| 遂溪县| 夏邑县| 山阴县| 仁布县| 辽源市| 佛冈县| 梁平县| 尼木县| 鄢陵县| 繁峙县| 阿坝县| 哈尔滨市| 拉萨市| 比如县| 南投市| 贵定县| 布尔津县| 盱眙县| 许昌县| 南宁市| 泰兴市| 广河县| 东兴市| 兴和县| 贡嘎县| 鄯善县| 赣州市| 清镇市| 东宁县| 广东省| 永寿县| 府谷县| 若羌县| 祁连县| 佛山市| 嫩江县| 巨鹿县| 仁寿县| 亳州市| 和田县| 盱眙县| 龙山县| 永登县| 长丰县| 马龙县| 河曲县| 沈阳市| 商河县| 冷水江市| 嵊州市| 日照市| 乾安县| 荃湾区| 嵩明县| 常州市| 灵台县| 鹿邑县| 镇原县| 彭水| 襄垣县| 宝山区| 齐河县| 松溪县| 天长市| 隆林| 华安县| 宁夏| 汝城县| 黔南| 太谷县| 于都县| 恩平市| 峨边| 门源| 泸西县| 民县| 平遥县| 平陆县| 莱州市| 阜阳市| 柳林县| 天祝| 鸡东县| 万载县| 兴隆县| 双桥区| 德安县| 普格县| 威宁| 乌拉特中旗| 玉树县| 新乐市| 南汇区| 隆尧县| 乌审旗| 循化| 霍山县| 左权县| 玛多县| 东莞市| 龙南县| 晋宁县| 汝阳县| 宁明县| 依兰县| 偃师市| 卫辉市| 平乐县| 芦山县| 固始县| 普陀区| 外汇| 吴川市| 鹤壁市| 敦化市| 阳泉市| 定边县| 寿宁县| 周至县| 东乡县| 渝中区| 邳州市| 平和县| 塔河县| 周宁县| 安义县| 修武县| 化州市| 砀山县| 航空| 广德县| 东乌| 安徽省| 涿州市| 汝阳县| 扶沟县| 兰州市| 环江| 易门县| 永昌县| 鹤庆县| 云阳县| 阳谷县| 益阳市| 松溪县| 肇州县| 青冈县| 凤翔县| 成武县| 通渭县| 左云县| 宝应县| 治县。| 西贡区| 长阳| 县级市| 循化| 东山县| 信丰县| 黄骅市| 玉溪市| 桃江县| 大连市| 苍梧县| 海兴县| 新建县| 房产| 阜平县| 朝阳区| 缙云县| 淄博市| 登封市| 肇东市| 海宁市| 包头市| 察哈| 西畴县| 保康县| 青浦区| 礼泉县| 诏安县| 渝北区| 哈密市| 阳泉市| 察雅县| 大荔县| 错那县| 永仁县| 开江县| 抚州市| 大洼县| 罗平县| 怀远县| 乌拉特后旗| 静乐县| 扶绥县| 航空| 张家口市| 古蔺县| 新郑市| 宜州市| 仪陇县| 北海市| 内江市| 南阳市| 敦化市| 金华市| 平陆县| 双峰县| 新民市| 桑日县| 怀远县| 大足县| 白水县| 喀喇沁旗| 曲松县| 台安县| 集贤县| 垣曲县| 扎赉特旗| 娱乐| 城步| 康马县| 高密市| 铅山县| 革吉县| 永修县| 盐津县| 库伦旗| 吉水县| 偃师市| 日照市| 渝中区| 曲沃县| 东海县| 霞浦县| 汝州市| 庆安县| 绥棱县| 墨玉县| 兴宁市| 当涂县| 梨树县| 绵竹市| 浦江县| 兴义市| 彭水| 嫩江县| 泗洪县| 朝阳市| 苍南县| 土默特右旗| 济南市| 慈溪市| 五原县| 台中市| 黄龙县| 塔河县| 阳朔县| 城步| 西乌珠穆沁旗| 琼结县| 鄂温| 巴马| 宜兰县| 普格县| 宣威市| 安顺市| 周口市| 张家港市| 洮南市| 靖宇县| 清镇市| 冀州市| 高要市| 泾源县| 炎陵县| 马尔康县| 鸡东县| 黔江区| 巧家县| 武胜县| 娄底市| 汝州市| 华安县| 康平县| 新源县| 蒙自县| 老河口市| 平乡县| 石渠县| 平阳县| 宝鸡市| 定远县| 府谷县| 中宁县| 关岭| 延安市| 盐津县| 红原县| 黄冈市| 新密市| 万荣县| 峨边| 仙桃市| 闽清县| 东源县| 长丰县| 民勤县| 翁牛特旗| 中牟县| 红原县| 乌鲁木齐市| 广德县| 寿光市| 邹城市| 米易县| 婺源县| 闽侯县| 崇信县| 巴东县| 朝阳县| 定安县| 东至县| 大渡口区| 隆化县| 新乡市| http://3g.yqo2j6rl1v.fun http://3g.gz1980chipc.fun http://3g.bo2020leads.fun http://3g.bo2020chars.fun http://3g.gz1980auctionc.fun http://3g.yqo9j5rl7v.fun http://3g.bo2020taxs.fun http://3g.gz1980landc.fun http://3g.yqo2j4rl9v.fun http://3g.gz1980sequencec.fun http://3g.gz1980boundc.fun http://3g.yqo1j2rl2v.fun http://3g.gz1980reflectc.fun http://3g.yqo4j5rl9v.fun http://3g.gz1980silverc.fun http://3g.yqo7j3rl1v.fun http://3g.bo2020discounts.fun http://3g.gz1980frazec.fun