2019杭电多校训练第二场1002[线段树/树状数组+dp]

1002 Beauty Of Unimodal Sequence

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 293 Accepted Submission(s): 84

Problem Description
You are given an array of n integers a1,a2,…,an. We define that a sequence p1,p2,…,pk(k∈[1,n]) is beautiful if and only if these conditions are met:

∙ 1≤p1<p2<⋯<pk≤n.

∙ There exists t(t∈[1,k]) satisfying ap1<ap2<⋯apt+1>⋯>apk.

You need to find all the longest beautiful sequences, and output the lexicographically smallest one and the lexicographically largest one in them.

Check the examples below for better understanding.

Input
There are multiple test cases.

Each case starts with a line containing a positive integer n(n≤3×105).

The second line contains n integers a1,a2,…,an(1≤ai≤109).

It is guaranteed that the sum of Ns in all test cases is no larger than 106.

Output
For each test case, output two lines, the first of which depicts the lexicographically smallest one in longest beautiful sequences and the second of which depicts the lexicographically largest one in longest beautiful sequences.

Sample Input
7
1 4 2 5 7 4 6
3
1 2 3
3
3 2 1

Sample Output
1 2 4 5 6
1 3 4 5 7
1 2 3
1 2 3
1 2 3
1 2 3

Source
2019 Multi-University Training Contest 2

题意：给一个序列，在满足单调递增或者单调递减或者先增后减的最长子序列集合里找到下标字典序最大以及最小的两个子序列，输出这两个子序列里元素的下标

题解：先确定字典序的问题：通过观察不难发现满足条件的最长子序列中下标最小的子序列中元素各个位置的下标都是最小的，即第一个元素是所有满足条件的第一元素中下标最小的，第二元素是第二元素中下标最小的…所以贪心地选择第一个第一元素和第一个第二元素…第一个第k元素即可得到最小字典序的方案，同理选择倒数第一个第k元素…倒数第一个第二元素，倒数第一个第一元素即可得到最大字典序的方案。
所以问题就变成了怎么快速寻找满足条件的第一个某一元素，那么就需要通过快速判断某个元素被选取之后是否能得到满足条件的序列并且这个元素在最终序列扮演的第几元素是否已经被选取过。
考虑到某个元素在结果序列中的位置可能处在上升段或者下降段，如果处于上升段那么这个结果序列就可以由以当前元素为结尾的最长上升序列和以当前元素为开头的最长单峰或者下降或者上升序列拼接成，同理如果处于下降段那么这个结果序列就可以由以当前元素为结尾的最长单峰或者下降序列和以当前元素为开头的最长下降序列拼接成。
很容易想到可以使用dp求出这些，定义dp[0][i]表示以i为结尾的最长上升子序列的长度，dp[1][i]表示以i为开头的最长下降子序列的长度，dp[2][i]表示以i为结尾的单峰子序列的长度，dp[3][i]表示以i为开头的单峰子序列的长度。求解dp[0][i]和dp[1][i]很容易使用二分优化到nlogn，求解dp[2][i]和dp[3][i]的时候离散化然后借助线段树快速求出区间[a[i]+1,siz]的dp最大值将复杂度降至nlogn，由于区间的右端点总是整个区间的右端点，所以也可以使用树状数组求出区间[a[i]+1,siz]的dp最大值，注意如果右端点不总是整个区间的最右端，使用树状数组求区间最值相对复杂。比如如果求1 2 3 4 3中[2,5]的最大值，那么只需要将每个元素a[i]更新[1,a[i]]内各个区间的最值即可，而求[2,3]就不能简单地通过更新[1,a[i]]内各个区间最值求得，因为前者由于右端点总是整个区间最右端所以每个元素一定会覆盖左边区间的每个点 (好像扯远了…)

线段树求区间最值+dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" is "<<x<<endl;
const int maxn=3e5+5;
int a[maxn],b[maxn],dp[4][maxn],ac1[maxn],ac2[maxn];
struct node{
    int l;
    int r;
    int maxx;
}nod[maxn<<3];
void pushup(int rt){
    nod[rt].maxx=max(nod[rt<<1].maxx,nod[(rt<<1)|1].maxx);
}
void build(int l,int r,int rt){
    nod[rt].l=l;
    nod[rt].r=r;
    if(l==r){
        nod[rt].maxx=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,(rt<<1)|1);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(l>=L&&R>=r)return nod[rt].maxx;
    int mid=(l+r)>>1;
    int xx=0;
    if(mid>=L)xx=max(xx,query(L,R,l,mid,rt<<1));
    if(mid<R)xx=max(xx,query(L,R,mid+1,r,(rt<<1)|1));
    return xx;
}
void update(int x,int val,int l,int r,int rt){
    if(l==r){
        nod[rt].maxx=max(val,nod[rt].maxx);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)update(x,val,l,mid,rt<<1);
    else update(x,val,mid+1,r,(rt<<1)|1);
    pushup(rt);
}
int main(){
    int n;
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        int top=0;
        for(int i=1;i<=n;i++){
            if(top==0){b[++top]=a[i];dp[0][i]=1;}
            else if(a[i]>b[top]){b[++top]=a[i];dp[0][i]=top;}
            else{int pos=lower_bound(b+1,b+1+top,a[i])-b;dp[0][i]=pos;b[pos]=a[i];}
        }
        top=0;
        for(int i=n;i>=1;i--){
            if(top==0){b[++top]=a[i];dp[1][i]=1;}
            else if(a[i]>b[top]){b[++top]=a[i];dp[1][i]=top;}
            else{int pos=lower_bound(b+1,b+1+top,a[i])-b;dp[1][i]=pos;b[pos]=a[i];}
        }
        int ans=1;
        for(int i=1;i<=n;i++){
            ans=max(ans,dp[0][i]+dp[1][i]-1);
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        int siz=unique(b+1,b+1+n)-(b+1);
        build(1,siz,1);
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
        for(int i=1;i<=n;i++){
            int w=query(a[i]+1,siz,1,siz,1);
            dp[2][i]=w+1;
            update(a[i],max(dp[2][i],dp[0][i]),1,siz,1);
        }
        build(1,siz,1);
        for(int i=n;i>=1;i--){
            int w=query(a[i]+1,siz,1,siz,1);
            dp[3][i]=w+1;
            update(a[i],max(dp[3][i],dp[1][i]),1,siz,1);
        }
        int tot=1;
        for(int i=1;i<=n;i++){
            if((dp[2][i]+dp[1][i]-1==ans&&dp[2][i]==tot)||
               (dp[3][i]+dp[0][i]-1==ans&&dp[0][i]==tot)||
               dp[1][i]+dp[0][i]-1==ans&&dp[0][i]==tot){
                ac1[tot]=i;
                tot++;
               }
        }
        tot=ans;
        for(int i=n;i>=1;i--){
            if((dp[2][i]+dp[1][i]-1==ans&&dp[1][i]==ans-tot+1)||
               (dp[3][i]+dp[0][i]-1==ans&&dp[3][i]==ans-tot+1)||
               dp[1][i]+dp[0][i]-1==ans&&dp[1][i]==ans-tot+1){
                ac2[tot]=i;
                tot--;
               }
        }
        for(int i=1;i<=ans;i++){
            printf("%d",ac1[i]);
            char cc=(i==ans)?'\n':' ';
            printf("%c",cc);
        }
        for(int i=1;i<=ans;i++){
            printf("%d",ac2[i]);
            char cc=(i==ans)?'\n':' ';
            printf("%c",cc);
        }
    }
    return 0;
}

树状数组求区间最值+dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" is "<<x<<endl;
const int maxn=3e5+5;
int a[maxn],b[maxn],dp[4][maxn],c[maxn],ac1[maxn],ac2[maxn];
int lowbit(int x){
    return x&(-x);
}
void update(int x,int val){
    for(int i=x;i>0;i-=lowbit(i)){
        c[i]=max(c[i],val);
    }
}
int query(int x, int y)
{
    int xx=0;
    for(int i=x;i<=y;i+=lowbit(i)){
        xx=max(c[i],xx);
    }
    return xx;
}
int main(){
    int n;
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        int top=0;
        for(int i=1;i<=n;i++){
            if(top==0){b[++top]=a[i];dp[0][i]=1;}
            else if(a[i]>b[top]){b[++top]=a[i];dp[0][i]=top;}
            else{int pos=lower_bound(b+1,b+1+top,a[i])-b;dp[0][i]=pos;b[pos]=a[i];}
        }
        top=0;
        for(int i=n;i>=1;i--){
            if(top==0){b[++top]=a[i];dp[1][i]=1;}
            else if(a[i]>b[top]){b[++top]=a[i];dp[1][i]=top;}
            else{int pos=lower_bound(b+1,b+1+top,a[i])-b;dp[1][i]=pos;b[pos]=a[i];}
        }
        int ans=1;
        for(int i=1;i<=n;i++){
            ans=max(ans,dp[0][i]+dp[1][i]-1);
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        int siz=unique(b+1,b+1+n)-(b+1);
        for(int i=0;i<=siz;i++)c[i]=0;
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
        for(int i=1;i<=n;i++){
            int w=query(a[i]+1,siz);
            dp[2][i]=w+1;
            update(a[i],max(dp[2][i],dp[0][i]));
        }
        for(int i=0;i<=siz;i++)c[i]=0;
        for(int i=n;i>=1;i--){
            int w=query(a[i]+1,siz);
            dp[3][i]=w+1;
            update(a[i],max(dp[3][i],dp[1][i]));
        }
        int tot=1;
        for(int i=1;i<=n;i++){
            if((dp[2][i]+dp[1][i]-1==ans&&dp[2][i]==tot)||
               (dp[3][i]+dp[0][i]-1==ans&&dp[0][i]==tot)||
               dp[1][i]+dp[0][i]-1==ans&&dp[0][i]==tot){
                ac1[tot]=i;
                tot++;
               }
        }
        tot=ans;
        for(int i=n;i>=1;i--){
            if((dp[2][i]+dp[1][i]-1==ans&&dp[1][i]==ans-tot+1)||
               (dp[3][i]+dp[0][i]-1==ans&&dp[3][i]==ans-tot+1)||
               dp[1][i]+dp[0][i]-1==ans&&dp[1][i]==ans-tot+1){
                ac2[tot]=i;
                tot--;
               }
        }
        for(int i=1;i<=ans;i++){
            printf("%d",ac1[i]);
            char cc=(i==ans)?'\n':' ';
            printf("%c",cc);
        }
        for(int i=1;i<=ans;i++){
            printf("%d",ac2[i]);
            char cc=(i==ans)?'\n':' ';
            printf("%c",cc);
        }
    }
    return 0;
}