首页 > 代码库 > Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞
Codeforces Round #277 E. LIS of Sequence(486E) 树状数组乱搞
http://codeforces.com/contest/486/problem/E
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.
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).
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.
1 4
3
4 1 3 2 5
3223
4 1 5 2 3
3133
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) 树状数组乱搞