首页 > 代码库 > Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞

Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞

2024-08-02 00:59:12   220人阅读

http://codeforces.com/contest/486/problem/E

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:

  1. group of all i such that ai belongs to no longest increasing subsequences.
  2. group of all i such that ai belongs to at least one but not every longest increasing subsequence.
  3. 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都出现的。

思路：由于有10^5个数，用树状数组优化正序求下LIS,f[i]记录到每个数产生的LIS是多少,然后再倒序求一遍最长下降子序列，g[i]记下每个数产生的值是多少。然后扫描一遍，如果f[i]+g[i]-1<maxlen，那么a[i]肯定是LIS中不需要的,把所有需要的f[i]值加入到一个map或者vector里，如果改值出现两次以上，那么就是可有可无的，出现一次的就是必需的。

貌似还有一种二分的方法。。比赛完再补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 <cstdio>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <set>
#include <map>
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\n",a)
typedef pair<int,int> 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<int>q[N];
    for(int i=1;i<=n;i++)
    {
        if(f[i]+g[i]-1<res)
            ans[i]=1;
        else q[f[i]].pb(i);
    }
    for(int i=1;i<=res;i++)
    {
        int sz=q[i].size();
        for(int j=0;j<sz;j++)
        {
            int v=q[i][j];
            if(sz==1) ans[v]=3;
            else ans[v]=2;
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d",ans[i]);
    puts("");
    return 0;
}


Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞


联系
我们