Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞 - c++编程基础

E. LIS of Sequence time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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

input

4
1 3 2 5

output

input

4
1 5 2 3

output

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都出现的。

思路：由于有10^5个数，用树状数组优化正序求下LIS,f[i]记录到每个数产生的LIS是多少,然后再倒序求一遍最长下降子序列，g[i]记下每个数产生的值是多少。然后扫描一遍，如果f[i]+g[i]-1

貌似还有一种二分的方法。。比赛完再补233.

树状数组可以很方便求这种区间1到i的最值。并且树状数组还可以求任意区间最值，http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html?ADUIN=1242923069&ADSESSION=1415787976&ADTAG=CLIENT.QQ.5365_.0&ADPUBNO=26405不过不好理解，还是线段树好。

/**
 * @author neko01
 */
//#pragma comment(linker, /STACK:102400000,102400000)
#include 
    
     
#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              using namespace std; typedef long long LL; #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define pb push_back #define mp(a,b) make_pair(a,b) #define clr(a) memset(a,0,sizeof a) #define clr1(a) memset(a,-1,sizeof a) #define dbg(a) printf(%d ,a) typedef pair
              
                pp; const double eps=1e-8; const double pi=acos(-1.0); const int INF=0x3f3f3f3f; const LL inf=(((LL)1)<<61)+5; const int N=100005; int f[N]; int g[N]; int a[N]; int bit[N]; int ans[N]; int sum1(int x) { int ans=0; for(int i=x;i>0;i-=i&-i) ans=max(bit[i],ans); return ans; } void add1(int x,int val) { for(int i=x;i<=N;i+=i&-i) bit[i]=max(bit[i],val); } int sum2(int x) { int ans=0; for(int i=x;i<=N;i+=i&-i) ans=max(bit[i],ans); return ans; } void add2(int x,int val) { for(int i=x;i>0;i-=i&-i) bit[i]=max(bit[i],val); } int main() { int n,res=0; scanf(%d,&n); for(int i=1;i<=n;i++) { scanf(%d,&a[i]); int x=sum1(a[i]-1); f[i]=x+1; if(f[i]>res) res=f[i]; add1(a[i],f[i]); } clr(bit); for(int i=n;i>=1;i--) { int x=sum2(a[i]+1); g[i]=x+1; add2(a[i],g[i]); } vector
               
                q[N]; for(int i=1;i<=n;i++) { if(f[i]+g[i]-1
                
                 ?