E. LIS of Sequence（好题 LIS ）

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence a consisting of n (1 ≤ n ≤ 105) elements a1, a2, ..., an (1 ≤ ai ≤ 105). A subsequence ai1, ai2, ..., aik where1 ≤ i1 < i2 < ... < ik ≤ n is called increasing if ai1 < ai2 < ai3 < ... < aik. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups:

group of all i such that ai belongs to no longest increasing subsequences.
group of all i such that ai belongs to at least one but not every longest increasing subsequence.
group of all i such that ai belongs to every longest increasing subsequence.

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.

Input

The first line contains the single integer n (1 ≤ n ≤ 105) denoting the number of elements of sequence a.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 105).

Output

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index ibelongs to.

        Sample test(s) 
      
          input 
        
1
4

          output 
        
3

          input 
        
4
1 3 2 5

          output 
        
3223

          input 
        
4
1 5 2 3

          output 
        
3133

Note

In the second sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a1, a2, a4} = {1, 3, 5} and {a1, a3, a4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a1, a3, a4} = {1, 2, 3}.

大致题意：由于一个数列的LIS可能存在多个，问你哪些数是所有LIS都没出现的，哪些数是所有LIS都出现的。

思路：LIS要用二分的优化写nlogn的，这题问的是每个数相关的性质，所以求出两个dp，一个表示以ai为结尾LIS的长度，一个表示从ai开始的LIS的长度

当dp1[i]+dp2[i]-1！=LIS显然ai 没组成任何LIS，此时输出1

然后抓住两条不同LIS的性质，假设a[i]仅在某一条LIS上那么另一条LIS上必然有dp1[j]=dp1[i] 或dp2[j]=dp2[i]; 此时对于a[i]输出2

否则输出3

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>

using namespace std;

const int N = 1e5+100;
int a[N];
int b[N];
int tp[N];
int dpf[N],dpb[N];
const int inf =0x3f3f3f3f;
bool flag[N];
int vis[N];
int n;
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) b[i]=a[n-i+1];
    memset(tp,0x3f,sizeof(tp));
    int LIS=1;
    for(int i=1;i<=n;i++)
    {
        int * p=lower_bound(tp+1,tp+1+n,a[i]);
        *p=a[i];
        dpf[i]=p-tp;
        LIS=max(LIS,dpf[i]);
    }
    memset(tp,-1,sizeof(tp));tp[0]=inf;
    for(int i=1;i<=n;i++)
    {
        int l=0,r=n+1;
        while(r-l>1)
        {
            int m=(l+r)>>1;
            if(tp[m]>b[i]) l=m;
            else r=m;
        }
        tp[l+1]=b[i];
        dpb[n-i+1]=l+1;
    }
    for(int i=1;i<=n;i++) if(dpf[i]+dpb[i]-1==LIS) flag[i]=1,vis[dpf[i]]++;
    for(int i=1;i<=n;i++)
        if(flag[i]==0) printf("1");
        else if(flag[i]&&vis[dpf[i]]>1) printf("2");
        else printf("3");
    return 0;
}

秒客网

E. LIS of Sequence（好题 LIS ）

相关文章