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

题目链接
大意：给你一个数组，让你求出最长的字典序最大和最小的(先升后降)单峰子序列
思路：考虑dp
$L [i] [0] 表示 a [i] 一定取，序列 a [1.. i] 的最长上升子序列长度。$
$L [i] [1] 表示 a [i] 一定取，序列 a [1.. i] 的最长单峰子序列长度。$
$R [i] [0] 表示 a [i] 一定取，序列 a [i . . n] 的最长下降子序列长度。$
$R [i] [1] 表示 a [i] 一定取，序列 a [i . . n] 的最长单峰子序列长度。$
用树状数组求出每个数的四个参数，然后统计每个数所在的最长单峰子序列的长度，最大即为答案长度。
然后考虑字典序最小，我们从前往后遍历，能选就选
判断一下当前是上升还是下降，
1.如果是上升的话：
1）那么如果即将要选的这个数大于 $p r e$ 且它的 $R [i] [1]$ 满足条件我们就选，后续还可能继续上升，如果 $R [i] [0]$ 满足条件，那么显然后续就会下降，
2）如果当前这个数小于之前的数，且 $R [i] [0]$ 满足条件我们就可以取，后续变成下降。
2.如果是下降的话：
1）那么这个数必须小于之前的数且 $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;
}