hdu6592 Beauty Of Unimodal Sequence（树状数组+贪心）

题目链接
大意：给你一个数组，让你求出最长的 字典序最大和最小的(先升后降)单峰子序列
思路：考虑dp
$L\left[i\right]\left[0\right]表示a\left[i\right]一定取，序列a\left[\mathrm{1..}i\right]的最长上升子序列长度。$L[i][0]表示a[i]一定取，序列a[1..i]的最长上升子序列长度。
$L\left[i\right]\left[1\right]表示a\left[i\right]一定取，序列a\left[\mathrm{1..}i\right]的最长单峰子序列长度。$L[i][1]表示a[i]一定取，序列a[1..i]的最长单峰子序列长度。
$R\left[i\right]\left[0\right]表示a\left[i\right]一定取，序列a\left[i..n\right]的最长下降子序列长度。$R[i][0]表示a[i]一定取，序列a[i..n]的最长下降子序列长度。
$R\left[i\right]\left[1\right]表示a\left[i\right]一定取，序列a\left[i..n\right]的最长单峰子序列长度。$R[i][1]表示a[i]一定取，序列a[i..n]的最长单峰子序列长度。
用树状数组求出每个数的四个参数，然后统计每个数所在的最长单峰子序列的长度，最大即为答案长度。
然后考虑字典序最小，我们从前往后遍历，能选就选
判断一下当前是上升还是下降，
1.如果是上升的话：
1）那么如果即将要选的这个数大于 $pre$pre且它的 $R\left[i\right]\left[1\right]$R[i][1]满足条件我们就选，后续还可能继续上升，如果 $R\left[i\right]\left[0\right]$R[i][0]满足条件，那么显然后续就会下降，
2）如果当前这个数小于之前的数，且 $R\left[i\right]\left[0\right]$R[i][0]满足条件我们就可以取，后续变成下降。
2.如果是下降的话：
1）那么这个数必须小于之前的数且 $R\left[i\right]\left[0\right]$R[i][0]也要满足条件。
字典序最大就倒过来求一次字典序最小，跟上面差不多讨论。
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 3e5 +11;
int n,a[N];
int t[N],p[N];
void u1(int k,int d){
    for(;k<=n;k+=k&-k)t[k]=max(t[k],d);
}
void u2(int k,int d){
    for(;k;k-=k&-k)p[k]=max(p[k],d);
}
int g1(int k){
    int ans=0;
    for(;k;k-=k&-k)ans=max(ans,t[k]);
    return ans;
}
int g2(int k){
    int ans=0;
    for(;k<=n;k+=k&-k)ans=max(ans,p[k]);
    return ans;
}
int L[N][3],R[N][3],b[N],f[N];
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        for(int i=1;i<=n;i++)t[i]=0,f[i]=0,p[i]=0;
        for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
        for(int i=1;i<=n;i++){
            L[i][0]=g1(a[i]-1)+1;
            u1(a[i],L[i][0]);
            L[i][1]=g2(a[i]+1)+1;
            u2(a[i],max(L[i][0],L[i][1]));
        }
        for(int i=1;i<=n;i++)t[i]=0,f[i]=0,p[i]=0;
        int M=0;
        for(int i=n;i>=1;i--){
            R[i][0]=g1(a[i]-1)+1;
            u1(a[i],R[i][0]);
            R[i][1]=g2(a[i]+1)+1;
            u2(a[i],max(R[i][0],R[i][1]));    
            f[i]=max(L[i][0]+R[i][0]-1,max(L[i][0]+R[i][1]-1,L[i][1]+R[i][0]-1));
            M=max(M,f[i]);
        }    
        vector<int>A,B;
        int sta=0,pre=0;
        for(int i=1;i<=n&&A.size()<M;i++){
            if(f[i]!=M)continue;
            if(!sta){
                if(a[i]>pre&&R[i][1]+(int)A.size()>=M){
                    A.pb(i);
                    pre=a[i];
                }else if(a[i]<pre&&R[i][0]+(int)A.size()>=M){
                    sta=1;
                    pre=a[i];
                    A.pb(i);
                }else if(a[i]>pre&&R[i][0]+(int)A.size()>=M){
                    A.pb(i);
                    pre=a[i];
                    sta=1;
                }
            }else{
                if(a[i]<pre&&R[i][0]+(int)A.size()>=M){
                    A.pb(i);
                    pre=a[i];
                }
            }
        }
        sta=0;pre=0;
        for(int i=n;i>=1&&B.size()<M;i--){
            if(f[i]!=M)continue;
            if(!sta){
                if(a[i]>pre&&L[i][1]+(int)B.size()>=M){
                    B.pb(i);
                    pre=a[i];
                }else if(a[i]>pre&&L[i][0]+(int)B.size()>=M){
                    B.pb(i);
                    sta=1;
                    pre=a[i];
                }else if(a[i]<pre&&L[i][0]+(int)B.size()>=M){
                    B.pb(i);
                    sta=1;
                    pre=a[i];
                }
            }else{
                if(a[i]<pre&&L[i][0]+(int)B.size()>=M){
                    B.pb(i);
                    pre=a[i];
                }
            }            

        }
        reverse(B.begin(),B.end());
        for(int i=0;i<A.size();i++){
            cout<<A[i]<<(i==((int)A.size()-1)?'\n':' ');
        }
        for(int i=0;i<B.size();i++){
            cout<<B[i]<<(i==((int)B.size()-1)?'\n':' ');
        }        
    }    
    return 0;
}