首页 > 代码库 > Counting Sequences_线段树
Counting Sequences_线段树
Description
For a set of sequences of integers{a1,a2,a3,...an}, we define a sequence{ai1,ai2,ai3...aik}in which 1<=i1<i2<i3<...<ik<=n, as the sub-sequence of {a1,a2,a3,...an}. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence{ai1,ai2,ai3...aik},if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.
Input
Multiple test cases The first line will contain 2 integers n, d(2<=n<=100000,1<=d=<=10000000) The second line n integers, representing the suquence
Output
The number of Perfect Sub-sequences mod 9901
Sample Input
4 2 1 3 7 5
Sample Output
4
【题意】给一个数字序列,问长度大于2的且相邻两个数的差的绝对值不大于d的情况对9901取余
【思路】对于当前的数A,那么以它为最后一个元素可以组成的情况是A-d到A+d的和,也可以这样想,A-d的已经组成了m种情况,那么在不影响小于d的情况下,可以直接将A放到A-d组成的左右序列中,那么直接加就可以了,而后更新A可以组成的情况,数据太大还需要离散化,然后二分找一下A-d和A+d的位置,数据可能没有这两个位置,那么找到第一个大于等于A-d和第一个小于等于A+d的位置更新就行,且不会影响结果。
参考:http://blog.csdn.net/dan__ge/article/details/51620024
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=100000+10; const int mod=9901; int a[N],x[N],sum[4*N]; int n,m,nn,cnt; void build(int k,int l,int r)//建树 { sum[k]=0; if(l==r) return ; int mid=l+r>>1; build(2*k,l,mid); build(2*k+1,mid+1,r); } void update(int ll,int rr,int k,int l,int r) { if(l==r) { sum[k]=(sum[k]+rr)%mod; return ; } int mid=l+r>>1; if(mid>=ll) update(ll,rr,k*2,l,mid); if(mid<ll) update(ll,rr,k*2+1,mid+1,r);// sum[k]=(sum[k*2]+sum[k*2+1])%mod; } int query(int ll,int rr,int k,int l,int r) { if(ll<=l&&r<=rr) return sum[k]%mod; int mid=l+r>>1; int res=0; if(ll<=mid) res+=query(ll,rr,k*2,l,mid); if(mid<rr) res+=query(ll,rr,k*2+1,mid+1,r); return res%mod; } int main() { while(~scanf("%d%d",&n,&m)) { cnt=0; for(int i=0;i<n;i++) { scanf("%d",&a[i]); x[cnt++]=a[i]; x[cnt++]=a[i]-m; x[cnt++]=a[i]+m; } sort(x,x+cnt); nn=unique(x,x+cnt)-x;//nn去重后,不重复元素的个数;STLunqiue在STL中unique函数是一个去重函数,unique的功能是去除相邻的重复元素(只保留一个),
//其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后 返回去重后最后一个元素的地址,
//因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。 build(1,1,nn); int ans=0; for(int i=0;i<n;i++) { int p=lower_bound(x,x+nn,a[i])-x;//Lower_bound是小于等于关键字的位置 int left=lower_bound(x,x+nn,a[i]-m)-x; int right=lower_bound(x,x+nn,a[i]+m)-x; int c=query(left+1,right+1,1,1,nn); update(p+1,c+1,1,1,nn); ans=(ans+c)%mod; } printf("%d\n",ans); } return 0; }
Counting Sequences_线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。