|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3450
  /**//*
 题意：
给定N(N <= 100000)个数字ai和一个H，要求求出特殊序列的数量
，所谓特殊序列，就是相邻两个数字的绝对值小于等于H并且序列长度
大于等于2。
解法：
树状数组 + 动态规划
思路：
首先我们利用dp[i]表示到第i个位置能够找到的相邻数字之差小
于等于H的长度大于等于1的序列的总和，那么有状态转移方程
dp[i] = sum{ dp[j], j<i, abs(a[j]-a[i]) <= H }，这个做法的时间
复杂度是O(n^2)，但是n很大，所以不能采用，但是我们观察到这个转移
方程是以求和的形式出现，并且有一个限制条件就是abs(a[j]-a[i])<=H
，我们可以把它简写成a[i]-H <= a[j] <= a[i]+H，那么如果我们把数
字映射到下标，并且通过二分找到a[j]的范围，就可以轻松的通过树状
数组的成段求和来统计了。
具体做法是：由于数字较大，我们可以先将所有数字离散化，这样
每个数字就有一个 <= n 的标号，然后这个标号就可以对应树状数组的
下标了，每次从左往右在树状数组中统计[a[i]-H, a[i]+H]的解的数量
（注意，这里需要找到离散后对应的数字），然后将当前数字（离散后
的数字）插入到树状数组中，值即为先前找到的节的数量，循环结束，
累加和就是序列大于等于1的解的数量，然后再减去n就是最后的答案了
，这里注意是取模，并且保证答案不能为负数。
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010
#define mod 9901
int n;
int val[maxn], t[maxn], c[maxn];
int tot;
int lowbit(int x)  {
return x & (-x);
}
void add(int pos, int v) {
  while(pos <= tot) {
c[pos] += v;
if(c[pos] >= mod )
c[pos] %= mod;
pos += lowbit(pos);
 }
}
int sum(int pos) {
int s = 0;
while(pos >= 1) {
s += c[pos];
if(s >= mod )
s %= mod;
pos -= lowbit(pos);
}
return s;
}
int Bin(int v) {
int l = 1;
int r = tot;
while(l <= r) {
int m = (l + r) >> 1;
if(v == t[m])
return m;
if(v > t[m])
l = m + 1;
else
r = m - 1;
}
}
// 找到最小的大于等于它的数
int BThan(int v) {
int l = 1;
int r = tot;
int ans = 1;
while(l <= r) {
int m = (l + r) >> 1;
if(t[m] >= v) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
// 找到最大的小于等于它的数
int LThan(int v) {
int l = 1;
int r = tot;
int ans = tot;
while(l <= r) {
int m = (l + r) >> 1;
if(t[m] <= v) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
int H;
int main() {
int i;
while(scanf("%d %d", &n, &H) != EOF) {
for(i = 0; i < n; i++) {
scanf("%d", &val[i]);
t[i+1] = val[i];
}
tot = 0;
sort(t+1, t+1+n);
for(i = 1; i <= n; i++) {
if(i==1 || t[i] != t[i-1]) {
t[++tot] = t[i];
c[tot] = 0;
}
}
int ans = 0;
for(i = 0; i < n; i++) {
int nidx = Bin(val[i]);
int l = BThan(val[i] - H);
int r = LThan(val[i] + H);
int preVal = (sum(r) - sum(l-1)) % mod;
if(preVal < 0)
preVal += mod;
ans += preVal + 1; if(ans >= mod) ans %= mod;
add(nidx, preVal + 1);
}
printf("%d\n", ((ans - n) % mod + mod) % mod);
}
return 0;
}
|