2016 UESTC Training for Dynamic Programming N – 柱爷与子序列 树状数组

这题和N题有些相似之处^_^

题意：求所有相邻元素之差<=k的子序列数量

dp[i]表示以a[i]结尾的子序列数量

dp[i] = sum(dp[j])

0<j<i, a[i]-k<=a[j]<=a[i]+k

数值很大，先离散化

用线段树或树状数组记录dp[j]的区间和,   这里选了树状数组

单点更新，区间查询

dp=get(r) - get(l-1);

Update(x ,dp + 1);

要有+1 然后最后输出的时候 - n， 把多加了的1减掉

然后ans就是所以的dp值的和

注意点， 在树状数组里面也要进行取模，不然会溢出

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 100000 + 8, HASH = 1000000009;
int a[maxn], b[maxn], nn;
//LL dp[maxn];

LL Tree[maxn];

inline int lowbit(int x)
{
    return (x&-x);
}

void add(int x, LL value)
{
    for(int i = x; i <= nn; i += lowbit(i)) Tree[i] = (Tree[i] + value) % HASH; } LL get(int x) { LL sum = 0; for(int i = x; i; i -= lowbit(i)) sum =(sum + Tree[i]) % HASH; return sum; } //!WA7 然后直接给中间过程已经树状数组里面也直接全部取模了☺☺ int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); #endif // LOCAL int n, k, x, l, r; long long dp; //dp[maxn] ==>> dp
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    memcpy(b, a, sizeof a);
    sort(a, a + n);
    nn = unique(a, a + n) - a;

    memset(Tree, 0, sizeof Tree);
    for(int i = 0; i < n; i++){                            //!这里坐标统一为 1 ~ nn 了
        x = lower_bound(a, a + nn, b[i]) - a + 1;
        l = lower_bound(a, a + nn, b[i] - k) - a + 1;
        r = upper_bound(a, a + nn, b[i] + k) - a;          //返回最后一个b[i]的后面一个位置。
        //cout<<"x = "<<x<<" l = "<<l<<" r = "<<r<<endl;
        dp = (get(r) - get(l-1))%HASH;                            //有一个 l - 1的所以还是 1 ~ nn 好
        add(x, dp+1);                                      //修改的时候不能是0的不然 0&-0一直这样会死循环，当然，这里x 不会是0
    }
    printf("%lld", (get(nn) - n +HASH)%HASH); //ans 不是 dp[n-1] ☺☺
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx