锐客网

  1. 首页 > it技术 > >

BZOJ5157|BZOJ5157 & 洛谷3970（[TJOI2014]上升子序列——题解）

https://www.lydsy.com/JudgeOnline/problem.php?id=5157
https://www.luogu.org/problemnew/show/P3970

给定一个只包含整数的序列(序列元素的绝对值大小不超过10^9),你需要计算上升子序列的个数,满足如下条件的称之为一个上升子序列:
  1. 是原序列的一个子序列
  2. 长度至少为2
  3. 所有元素都严格递增
如果两个上升子序列相同,那么只需要计算一次。例如:序列{1,2,3,3}有4个上升子序列,分别为{1,2}{1,3},{1,2,3},{2,3}
sb题，但是（可能是因为我脑子不清晰的缘故）就是想不出来，看题解也死活看不懂，写完发现是真sb题……
于是疯狂深呼吸ing不然怕自己连题解都写不出来。
也不知道自己昨天是干了什么结果自己智商突然就飞了。
设f[i]为以i结尾的上升子序列个数，显然f[i]=sigma(f[j]+1)(1<=j 去重也很简单，离散化之后设g[i]为以数i结尾的上升子序列个数，用f更新g，最后累加g并且减去长度为1的序列即可。
然后就能想到把g搬到树状数组上维护，这样g[i]=sigma(g[j]+1)即可。
【BZOJ5157|BZOJ5157 & 洛谷3970（[TJOI2014]上升子序列——题解）】PS：为了方便统计，直接把g[i]+1扔到树状数组上就行了。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; const int N=1e5+5; const int p=1e9+7; inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)){w|=ch=='-'; ch=getchar(); } while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int n,lim,s[N],tr[N],f[N],pre[N],b[N]; inline int sum(int x,int y){ x+=y; if(x>=p)x-=p; return x; } inline int sub(int x,int y){ x-=y; if(x<0)x+=p; return x; } inline int lowbit(int t){return t&(-t); } inline void add(int x,int y){ for(int i=x; i<=lim; i+=lowbit(i))tr[i]=sum(tr[i],y); } inline int ask(int x){ int res=0; for(int i=x; i; i-=lowbit(i))res=sum(res,tr[i]); return res; } inline void LSH(){ sort(b+1,b+lim+1); lim=unique(b+1,b+lim+1)-b-1; for(int i=1; i<=n; i++) s[i]=lower_bound(b+1,b+lim+1,s[i])-b; } int main(){ n=read(); for(int i=1; i<=n; i++)s[i]=b[++lim]=read(); LSH(); for(int i=1; i<=n; i++){ f[i]=ask(s[i]-1)+1; add(s[i],sub(f[i],f[pre[s[i]]])); pre[s[i]]=i; } printf("%d\n",sub(ask(lim),lim)); return 0; }

+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。+
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
转载于:https://www.cnblogs.com/luyouqi233/p/9185854.html

    推荐阅读


    上一篇：GitHub如何下载单个文件夹

    下一篇：一线教师如何走出职业倦怠（）