|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3450
  /**//*
 題意：
給定N(N <= 100000)個(gè)數(shù)字ai和一個(gè)H，要求求出特殊序列的數(shù)量
，所謂特殊序列，就是相鄰兩個(gè)數(shù)字的絕對值小于等于H并且序列長度
大于等于2。
解法：
樹狀數(shù)組 + 動態(tài)規(guī)劃
思路：
首先我們利用dp[i]表示到第i個(gè)位置能夠找到的相鄰數(shù)字之差小
于等于H的長度大于等于1的序列的總和，那么有狀態(tài)轉(zhuǎn)移方程
dp[i] = sum{ dp[j], j<i, abs(a[j]-a[i]) <= H }，這個(gè)做法的時(shí)間
復(fù)雜度是O(n^2)，但是n很大，所以不能采用，但是我們觀察到這個(gè)轉(zhuǎn)移
方程是以求和的形式出現(xiàn)，并且有一個(gè)限制條件就是abs(a[j]-a[i])<=H
，我們可以把它簡寫成a[i]-H <= a[j] <= a[i]+H，那么如果我們把數(shù)
字映射到下標(biāo)，并且通過二分找到a[j]的范圍，就可以輕松的通過樹狀
數(shù)組的成段求和來統(tǒng)計(jì)了。
具體做法是：由于數(shù)字較大，我們可以先將所有數(shù)字離散化，這樣
每個(gè)數(shù)字就有一個(gè) <= n 的標(biāo)號，然后這個(gè)標(biāo)號就可以對應(yīng)樹狀數(shù)組的
下標(biāo)了，每次從左往右在樹狀數(shù)組中統(tǒng)計(jì)[a[i]-H, a[i]+H]的解的數(shù)量
（注意，這里需要找到離散后對應(yīng)的數(shù)字），然后將當(dāng)前數(shù)字（離散后
的數(shù)字）插入到樹狀數(shù)組中，值即為先前找到的節(jié)的數(shù)量，循環(huán)結(jié)束，
累加和就是序列大于等于1的解的數(shù)量，然后再減去n就是最后的答案了
，這里注意是取模，并且保證答案不能為負(fù)數(shù)。
 */
#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;
}
}
// 找到最小的大于等于它的數(shù)
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;
}
// 找到最大的小于等于它的數(shù)
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;
}
|