# Counting Sequences

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/65536 K (Java/Others)

Total Submission(s): 2335    Accepted Submission(s): 820

Problem 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

#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <map>

using namespace std;
const int maxn=1e5;
typedef long long int LL;
LL sum[maxn*8+5];
int n,d;
void pushup(int node)
{
sum[node]=sum[node<<1]+sum[node<<1|1];
sum[node]%=9901;
}
void update(int node,int l,int r,int val,LL num)
{
if(l==r)
{
sum[node]+=num;
sum[node]%=9901;
return;
}
int mid=(l+r)>>1;
if(val<=mid)
update(node<<1,l,mid,val,num);
else
update(node<<1|1,mid+1,r,val,num);
pushup(node);
}
LL query(int node,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
return sum[node]%9901;
int mid=(l+r)>>1;
LL ret=0;
if(L<=mid) ret+=query(node<<1,l,mid,L,R);
if(R>mid) ret+=query(node<<1|1,mid+1,r,L,R);
return ret%9901;
}
int a[maxn+5];
int c[maxn+5];
int b[maxn+5];
int cot;
int ans;

int fun1(int k,int tag)
{
int l=1,r=cot;
while(l<=r)
{
int mid=(l+r)/2;
if(k<a[mid])
r=mid-1;
else
l=mid+1;
}
if(tag) return l;
return r;
}
int fun2(int k)
{
int l=1,r=cot;
while(l<=r)
{
int mid=(l+r)/2;
if(k==a[mid])
return mid;
else if(k<a[mid])
r=mid-1;
else
l=mid+1;
}
return l;
}
int main()
{
while(scanf("%d%d",&n,&d)!=EOF)
{

memset(sum,0,sizeof(sum));

for( int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
c[i]=b[i];
}
sort(b+1,b+n+1);
cot=1;a[1]=b[1];
for(int i=2;i<=n;i++)
{
if(b[i]!=b[i-1])
a[++cot]=b[i];
}
for(int i=1;i<=n;i++)
{
int r=fun1(c[i],0)-1;
int l=fun1(c[i],1)+1;
int k=fun2(c[i]);

LL num=query(1,1,n,l,r);
ans+=num;
ans%=9901;
update(1,1,n,k,(num+1)%9901);
}
printf("%d\n",ans);
}

return 0;
}```

0 条评论

• ### LeetCode Contest 166

但是在用c++的快排的时候，被坑了，我一直的习惯是写自定义比较函数，没有写运算符重载，不知道为什么一直RE，浪费了挺多时间

• ### 天梯赛 大区赛 L3-014.周游世界 （Dijkstra）

L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

• ### 分治算法

// 二分查找的思路，halfLen 是中位数的right 所以必须 m + n + 1 // 中位数是可以将数组分割为左右相等的数组，一个数将其分为左右相等...

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### gcd，哈希问题-LeetCode 357、355、365、367、380

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（26）：3.5二分图匹配（1）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（28）：3.5最小费用流

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...