题目描述
数组A包含N个整数(可能包含相同的值)。设S为A的子序列且S中的元素是递增的,则S为A的递增子序列。如果S的长度是所有递增子序列中最长的,则称S为A的最长递增子序列(LIS)。A的LIS可能有很多个。例如A为:{1 3 2 0 4},1 3 4,1 2 4均为A的LIS。给出数组A,求A的LIS有多少个。由于数量很大,输出Mod 1000000007的结果即可。相同的数字在不同的位置,算作不同的,例如 {1 1 2} 答案为2。
Input
第1行:1个数N,表示数组的长度。(1 <= N <= 50000)第2 - N + 1行:每行1个数A[i],表示数组的元素(0 <= A[i] <= 10^9)
Output
输出最长递增子序列的数量Mod 1000000007。
Input示例
513204
Output示例
2
Solution
转移十分显而易见
f[i].x表示长度,f[i].y表示当前长度的个数.
f[i].x=max{f[j].y}+1,a[j]<a[i]
f[i].y=∑f[j].y,f[j].x=f[i].x-1
可以用线段树或是BIT来维护最大值以及最大值出现的个数log转移即可
Code
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define rep(i,s,t) for(int i=s;i<=t;i++) 7 #define dwn(i,s,t) for(int i=s;i>=t;i--) 8 #define clr(x,c) memset(x,c,sizeof(x)) 9 #define lson l,mid,x<<110 #define rson mid+1,r,x<<1|111 int read(){12 int x=0;char c=getchar();13 while(!isdigit(c)) c=getchar();14 while(isdigit(c)) x=x*10+c-'0',c=getchar();15 return x;16 }17 const int nmax=5e4+5;18 const int inf=0x7f7f7f7f;19 const int mod=1e9+7;20 int a[nmax],b[nmax],mx[nmax<<2],sm[nmax<<2];21 int qmax(int tl,int tr,int l,int r,int x){22 if(tl<=l&&tr>=r) return mx[x];23 int mid=(l+r)>>1,ans=0;24 if(tl<=mid) ans=max(ans,qmax(tl,tr,lson));25 if(tr>mid) ans=max(ans,qmax(tl,tr,rson));26 return ans;27 }28 int query(int tl,int tr,int p,int l,int r,int x){29 if(tl<=l&&tr>=r) return mx[x]==p?sm[x]:0;30 int mid=(l+r)>>1,ans=0;31 if(tl<=mid) ans+=query(tl,tr,p,lson);32 if(tr>mid) ans+=query(tl,tr,p,rson);33 return ans>=mod?ans-mod:ans;34 }35 void update(int p,int a,int b,int l,int r,int x){36 if(mx[x] >1;40 p<=mid?update(p,a,b,lson):update(p,a,b,rson);41 }42 void print(int l,int r,int x){43 printf("%d %d:%d %d\n",l,r,mx[x],sm[x]);44 if(l==r) return ;45 int mid=(l+r)>>1;46 print(lson);print(rson);47 }48 int main(){49 int n=read();50 rep(i,1,n)a[i]=b[i]=read();51 sort(b+1,b+n+1);52 int cnt=unique(b+1,b+n+1)-b-1;53 rep(i,1,n)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;54 int u,v,d;55 rep(i,1,n){56 u=a[i]==1?1:qmax(1,a[i]-1,1,cnt,1)+1;57 v=u==1?1:query(1,a[i]-1,u-1,1,cnt,1);58 update(a[i],u,v,1,cnt,1);59 }60 printf("%d\n",sm[1]);61 return 0;62 }