【（待重做）树状数组+dp+离散化】Counting Sequences

https://www.bnuoj.com/v3/contest_show.php?cid=9149#problem/G

【题意】

给定一个数组a，问这个数组有多少个子序列，满足子序列中任意两个相邻数的差（绝对值）都不大于d.

【思路】

首先，朴素的dp思想：

dp[i]为以a[i]结尾的子问题的答案，则dp[i]=sum(dp[k]),k<i&&|a[k]-a[i]|<=d

但是时间复杂度为O(n^2),会超时。

我们可以这样想：

如果数组a排好序后，dp[i]就是区间(a[i]-d,a[i]+d)的结果和（直接把a[i]加到原数组后面）

所以自然而然就想到了用树状数组,区间求和求出dp[i],然后单点修改dp[i]以备后用。

这样时间复杂度就变成了O(nlogn)

另外要注意原来是很稀疏的大数据，我们要离散化压缩状态（排序去重）

先把长度为1的姑且认为是完美子序列，然后再减去n,怎样状态就很好转移，所以看到代码里fi初始值为1.

【Accepted】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 
 8 using namespace std;
 9 const int mod=9901;
10 const int maxn=1e5+3;
11 int n,d;
12 int a[maxn],h[maxn],tree[maxn];
13 int lowbit(int x)
14 {
15     return x&(-x);
16  } 
17 void add(int k,int x)
18 {
19     while(k<=n)
20     {
21         tree[k]=(tree[k]+x)%mod;
22         k+=lowbit(k);
23     }
24 }
25 int query(int k)
26 {
27     int res=0;
28     while(k)
29     {
30         res=(res+tree[k])%mod;
31         k-=lowbit(k);
32     }
33     return res;
34 }
35 int query(int l,int r)
36 {
37     return (query(r)-query(l-1)+mod)%mod;
38 }
39 int main()
40 {    
41     while(~scanf("%d%d",&n,&d))
42     {
43         memset(tree,0,sizeof(tree));
44         for(int i=1;i<=n;i++)
45         {
46             scanf("%d",&a[i]);
47             h[i]=a[i];
48         }
49         sort(h+1,h+n+1);
50         int cnt=unique(h+1,h+n+1)-h-1;
51         int ans=0;
52         for(int i=1;i<=n;i++)
53         {
54             int fi=1;
55             int l=lower_bound(h+1,h+cnt+1,a[i]-d)-h;
56             int r=upper_bound(h+1,h+cnt+1,a[i]+d)-h-1;
57             int pos=lower_bound(h+1,h+cnt+1,a[i])-h;
58             fi=(fi+query(l,r))%mod;
59             ans=(ans+fi)%mod;
60             add(pos,fi);
61         }
62         ans=(ans-n%mod+mod)%mod;
63         cout<<ans<<endl;
64     }
65     return 0;
66 }

View Code

【知识点】

lower_bound返回第一个大于等于查找值的迭代器指针

upper_bound返回第一个大于（没有等于）查找值的迭代器指针