HDU6592 Beauty Of Unimodal Sequence（DP+树状数组）

/*
 * hdu6592
 * 题意：
 * 给你一个数组，让你求出最长的字典序最大的和最小的单峰子序列
 * 思路：
 * 考虑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]的最长单峰子序列长度
 * 用树状数组求出每个数的四个参数，然后统计出每个数所在的最长单峰子序列长度，最大即为答案长度
 * 然后考虑字典序最小，我们从前往后遍历，能选就选
 * 判断一下当前是上升还是下降
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=3e5+10;

int lowbit (int x) {
    return x&-x;
}

int N;
int a[maxn];
int c1[maxn],c2[maxn];

void update1 (int x,int val) {
    for (int i=x;i<=N;i+=lowbit(i)) c1[i]=max(c1[i],val);
}
void update2 (int x,int val) {
    for (int i=x;i;i-=lowbit(i)) c2[i]=max(c2[i],val);
}

int getsum1 (int x) {
    int ans=0;
    for (int i=x;i;i-=lowbit(i)) ans=max(ans,c1[i]);
    return ans;
}
int getsum2 (int x) {
    int ans=0;
    for (int i=x;i<=N;i+=lowbit(i)) ans=max(ans,c2[i]);
    return ans;
}

int L[maxn][3];
int R[maxn][3];
int b[maxn];
int dp[maxn];

int main () {
    while (~scanf("%d",&N)) {
        for (int i=1;i<=N;i++)
            c1[i]=0,c2[i]=0,dp[i]=0;
        for (int i=1;i<=N;i++)
            scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+1+N);
        int m=unique(b+1,b+1+N)-b-1;
        for (int i=1;i<=N;i++)
            a[i]=lower_bound(b+1,b+m+1,a[i])-b;
        for (int i=1;i<=N;i++) {
            L[i][0]=getsum1(a[i]-1)+1;
            update1(a[i],L[i][0]);
            L[i][1]=getsum2(a[i]+1)+1;
            update2(a[i],max(L[i][0],L[i][1]));
        }
        for (int i=1;i<=N;i++) c1[i]=0,c2[i]=0,dp[i]=0;
        int ans=0;
        for (int i=N;i>=1;i--) {
            R[i][0]=getsum1(a[i]-1)+1;
            update1(a[i],R[i][0]);
            R[i][1]=getsum2(a[i]+1)+1;
            update2(a[i],max(R[i][0],R[i][1]));
            dp[i]=max(L[i][0]+R[i][0]-1,max(L[i][0]+R[i][1]-1,L[i][1]+R[i][0]-1));
            ans=max(ans,dp[i]);
        }
        //printf("%d
",ans);
        vector<int> v1,v2;
        int pre=0;
        int st=0;
        for (int i=1;i<=N&&v1.size()<ans;i++) {
            if (dp[i]!=ans) continue;
            if (!st) {
                if (a[i]>pre&&R[i][1]+(int)v1.size()>=ans) {
                    v1.push_back(i);
                    pre=a[i];
                }
                else if (a[i]<pre&&R[i][0]+(int)v1.size()>=ans) {
                    st=1;
                    pre=a[i];
                    v1.push_back(i);
                }
                else if (a[i]>pre&&R[i][0]+(int)v1.size()>=ans) {
                    v1.push_back(i);
                    pre=a[i];
                    st=1;
                }
            }
            else {
                if (a[i]<pre&&R[i][0]+(int)v1.size()>=ans) {
                    v1.push_back(i);
                    pre=a[i];
                }
            }
        }
        st=0;
        pre=0;
        for (int i=N;i>=1&&v2.size()<ans;i--) {
            if (dp[i]!=ans) continue;
            if (!st) {
                if (a[i]>pre&&L[i][1]+(int)v2.size()>=ans) {
                    v2.push_back(i);
                    pre=a[i];
                }
                else if (a[i]>pre&&L[i][0]+(int)v2.size()>=ans) {
                    v2.push_back(i);
                    st=1;
                    pre=a[i];
                }
                else if (a[i]<pre&&L[i][0]+(int)v2.size()>=ans) {
                    v2.push_back(i);
                    st=1;
                    pre=a[i];
                }
            }
            else {
                if (a[i]<pre&&L[i][0]+(int)v2.size()>=ans) {
                    v2.push_back(i);
                    pre=a[i];
                }
            }
        }
        reverse(v2.begin(),v2.end());
        for (int i=0;i<v1.size();i++)
            printf("%d%s",v1[i],i<v1.size()-1?" ":"
");
        for (int i=0;i<v2.size();i++)
            printf("%d%s",v2[i],i<v2.size()-1?" ":"
");
    }
}