Counting Sequences
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 1872 Accepted Submission(s): 635
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.
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
Source
Recommend
线段树+dp，dp方程很简单,dp[i]表示以第i个元素结尾的完美序列的个数
dp[i] += dp[j] + 1(j < i)
先把数据离散化，然后按顺序插入到线段树上，维护区间和
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
__int64 dp[N];
int xis[N];
int arr[N];
int cnt;
struct node
{
int l, r;
__int64 sum;
}tree[N << 2];
int BinSearch(int val)
{
int l = 1, r = cnt, mid, ans;
while (l <= r)
{
mid = (l + r) >> 1;
if (xis[mid] == val)
{
ans = mid;
break;
}
else if (xis[mid] > val)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
int BinSearch_left(int val)
{
int l = 1;
int r = cnt, mid, ans;
while (l <= r)
{
mid = (l + r) >> 1;
if (xis[mid] >= val)
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
int BinSearch_right(int val)
{
int l = 1;
int r = cnt, mid, ans;
while (l <= r)
{
mid = (l + r) >> 1;
if (xis[mid] <= val)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return ans;
}
void build(int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
tree[p].sum = 0;
if (l == r)
{
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
void update(int p, int pos, __int64 val)
{
if (tree[p].l == tree[p].r)
{
tree[p].sum += val;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (pos <= mid)
{
update(p << 1, pos, val);
}
else
{
update(p << 1 | 1, pos, val);
}
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
tree[p].sum %= 9901;
}
__int64 query(int p, int l, int r)
{
if (tree[p].l >= l && tree[p].r <= r)
{
return tree[p].sum;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (r <= mid)
{
return query(p << 1, l, r);
}
else if (l > mid)
{
return query(p << 1 | 1, l, r);
}
else
{
return query(p << 1, l, mid) + query(p << 1 | 1, mid + 1, r);
}
}
int main()
{
int n, d;
while(~scanf("%d%d", &n, &d))
{
memset (dp, 0, sizeof(dp));
__int64 ans = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &arr[i]);
xis[i] = arr[i];
}
sort(xis + 1, xis + n + 1);
cnt = unique(xis + 1, xis + n + 1) - xis - 1;
build(1, 1, cnt);
dp[1] = 0;
update(1, BinSearch(arr[1]), dp[1] + 1);
int l, r;
for (int i = 2; i <= n; i++)
{
l = BinSearch_left(arr[i] - d);
r = BinSearch_right(arr[i] + d);
dp[i] = query(1, l, r);
dp[i] %= 9901;
int x = BinSearch(arr[i]);
update(1, x, dp[i] + 1);
ans += dp[i];
ans %= 9901;
}
printf("%I64d\n", ans);
}
return 0;
}