专栏首页算法修养HDU 3450 Counting Sequences(线段树)

HDU 3450 Counting Sequences(线段树)

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
思路:题目求满足要求的子串有多少个,那么我们应该固定序列的结尾点,dp[i],表示以i点为结尾的满足条件的序列有多少个,对于每一个点作为序列的最后一个点,都去找它前面所有满足条件的点k,然后加上dp[k],类似于动态规划,那么如何高效的求满足条件的点,即这个点前面的所有点,哪些是满足在a[i]-d,和a[i]+d.我们可以用线段树另外,需要离散化一下,这里时间只有1秒钟,如果用map离散会超时,所以我们可以用二分法离散#include <iostream>
#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,浪费了挺多时间

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

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

    ShenduCC
  • LeetCode Contest 180

    ShenduCC
  • 分治算法

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

    用户7625070
  • leetcode363. Max Sum of Rectangle No Larger Than K

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

    眯眯眼的猫头鹰
  • gcd,哈希问题-LeetCode 357、355、365、367、380

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

    算法工程师之路
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • 挑战程序竞赛系列(21):3.2反转

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

    用户1147447
  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

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

    用户1147447
  • 挑战程序竞赛系列(28):3.5最小费用流

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

    用户1147447

扫码关注云+社区

领取腾讯云代金券