首页 > 代码库 > 51nod1376 最长递增子序列的数量
51nod1376 最长递增子序列的数量
O(n2)显然超时。网上找的题解都是用奇怪的姿势写看不懂TAT。然后自己YY。要求a[i]之前最大的是多少且最大的有多少个。那么线段树维护两个值，一个是当前区间的最大值一个是当前区间最大值的数量那么我们可以做到O(logn)查询最大值和更新。
不过树状数组一直不怎么会用。。。
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define lson l,mid,x<<1#define rson mid+1,r,x<<1|1int read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=5e4+5;const int inf=0x7f7f7f7f;const int mod=1e9+7;int a[nmax],b[nmax],mx[nmax<<2],sm[nmax<<2];int qmax(int tl,int tr,int l,int r,int x){ if(tl<=l&&tr>=r) return mx[x]; int mid=(l+r)>>1,ans=0; if(tl<=mid) ans=max(ans,qmax(tl,tr,lson)); if(tr>mid) ans=max(ans,qmax(tl,tr,rson)); return ans;}int query(int tl,int tr,int p,int l,int r,int x){ if(tl<=l&&tr>=r) return mx[x]==p?sm[x]:0; int mid=(l+r)>>1,ans=0; if(tl<=mid) ans+=query(tl,tr,p,lson); if(tr>mid) ans+=query(tl,tr,p,rson); return ans>=mod?ans-mod:ans;}void update(int p,int a,int b,int l,int r,int x){ if(mx[x]<a) mx[x]=a,sm[x]=b; else if(mx[x]==a) sm[x]=(sm[x]+b)%mod; if(l==r) return ; int mid=(l+r)>>1; p<=mid?update(p,a,b,lson):update(p,a,b,rson);}void print(int l,int r,int x){ printf("%d %d:%d %d\n",l,r,mx[x],sm[x]); if(l==r) return ; int mid=(l+r)>>1; print(lson);print(rson);}int main(){ int n=read();rep(i,1,n) a[i]=b[i]=read(); sort(b+1,b+n+1);int cnt=unique(b+1,b+n+1)-b-1; rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b; int u,v,d; rep(i,1,n){ u=a[i]==1?1:qmax(1,a[i]-1,1,cnt,1)+1; v=u==1?1:query(1,a[i]-1,u-1,1,cnt,1); update(a[i],u,v,1,cnt,1); /*printf("->%d %d\n",u,v); printf("->_->\n");print(1,cnt,1);*/ } printf("%d\n",sm[1]); return 0;}
1376 最长递增子序列的数量
基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
收藏
关注数组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
51nod1376 最长递增子序列的数量
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。