链接： HDU6592 - Beauty Of Unimodal Sequence
题意：
含有 n 个正整数的序列 a[1]、a[2]、… 、a[n]，找出 最长的单峰序列（先严格递增后严格递减，允许仅严格递增或仅严格递减）。要求分别输出所有最长的单峰序列 字典序最小 和 字典序最大 的序列（按其下标排序，输出时也是输出下标）
分析：
先预处理得到这两个数组：
dec[i]：以 a[i] 开头的最长严格递减子序列长度
x[i]：以 a[i] 开头的最长单峰序列长度
若最长的单峰序列 长度为 L（即最大的x[i]），那么 构建字典序最小的序列，根据贪心原则，就是 从 1 遍历到 n，能选尽量选，这样就能保证得到字典序最小。
cnt：已放入答案序列中的元素个数
pre：上一个放入答案序列中的元素a
对于第 i 个元素a[i]：
若 a[i] > pre，则当 x[i] == L - cnt 时可以将a[i]放入
若 a[i] < pre，则当 dec[i] == L - cnt 时可以将a[i]放入
其他情况均不可放入。
这样就能保证选了 a[i] 之后还可以达到长度 L。 至于字典序最大，可以将a数组翻转一下，然后同样的方法再求解一遍，最后处理一下下标就行了。
预处理 dec[i]
要求以 a[i] 开头的最长严格递减子序列长度，可以从 n 向 1遍历，然后求以a[i]结尾的最长严格递增子序列长度，可以二分维护LIS，也可以用线段树。
线段树的话就要先离散化处理数组a，然后以 数的大小作为线段树下标，里面 维护已有的最大的 dec[i]，则 dec[i] = query( 1, a[i] - 1 ) +1
预处理 x[i]
同样地从 n 向 1遍历，然后变为求以a[i]结尾的最长单峰序列长度，离散化后线段树维护。
以 数的大小作为线段树下标，里面 维护已有的最大x[i]，(m表示数组a离散化后的最大值）
则 x[i] = max( query(a[i] +1, m) + 1 , dec[i] )
以下代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=3e5+10;
int t[4*maxn];
int n,m,a[maxn];
void init()
{
int b[maxn];for(int i=1;i<=n;i++)b[i]=a[i];sort(b+1,b+n+1);m=unique(b+1,b+n+1)-(b+1);for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
}
void updata(int rt,int l,int r,int x,int num)
{
if(l==r){
t[rt]=max(num,t[rt]); //不能直接令t[rt]=num，要维护最大的值return;}int mid=(l+r)>>1;if(x<=mid)updata(rt<<1,l,mid,x,num);elseupdata(rt<<1|1,mid+1,r,x,num);t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
int query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return t[rt];if(r<ql||l>qr)return 0;int mid=(l+r)>>1;return max(query(rt<<1,l,mid,ql,qr),query(rt<<1|1,mid+1,r,ql,qr));
}
int ans[maxn],cnt;
void solve()
{
int dec[maxn],x[maxn];memset(t,0,sizeof(t));for(int i=n;i>=1;i--){
if(a[i]-1>=1)dec[i]=query(1,1,m,1,a[i]-1)+1;elsedec[i]=1;updata(1,1,m,a[i],dec[i]); //更新}memset(t,0,sizeof(t));int L=0;for(int i=n;i>=1;i--){
if(a[i]+1<=m)x[i]=max(dec[i],query(1,1,m,a[i]+1,m)+1);elsex[i]=dec[i];updata(1,1,m,a[i],x[i]); //更新L=max(L,x[i]); //最长的单峰序列长度}int pre=0;cnt=0;for(int i=1;i<=n;i++){
if(a[i]>pre&&x[i]==L-cnt){
ans[++cnt]=i;pre=a[i];}else if(a[i]<pre&&dec[i]==L-cnt){
ans[++cnt]=i;pre=a[i];}elsecontinue;}}
int main()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);init();solve();for(int i=1;i<=cnt;i++){
if(i>1)printf(" ");printf("%d",ans[i]);}printf("\n");reverse(a+1,a+n+1); //翻转后求最大字典序solve();for(int i=cnt;i>=1;i--){
if(i<cnt)printf(" ");printf("%d",n-ans[i]+1);}printf("\n");}return 0;
}