程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2836 Traversal（線段樹+離散化+DP）

HDU 2836 Traversal（線段樹+離散化+DP）

編輯：C++入門知識

HDU 2836 Traversal（線段樹+離散化+DP）

題意：給你n個數的序列，一個數h，求相鄰數之差不超過h的子序列的個數和 % 9901。

思路：經典水題，顯然用d[i]表示以a[i]結尾的滿足條件的子序列個數。那麼對於j < i ， | a[j] - a[i] | <= h ，等價於 a[j] <= a[i] + h && a[j] >= a[i] - h。對於這個限制用線段樹下標維護，線段樹用來維護d[i]的累加和。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 9901;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m,sum[maxn<<2],h,d[maxn],a[maxn],b[maxn];
inline void add(int& a, int b) {
    a += b;
    if(a >= mod) a %= mod;
}
void pushup(int o) {
    sum[o] = sum[o<<1] + sum[o<<1|1];
    if(sum[o] >= mod) sum[o] %= mod;
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    sum[o] = 0;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    pushup(o);
}
void update(int L, int R, ll v, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        add(sum[o], v); return ;
    }
    if(L <= m) update(L, R, v, l, m, o<<1);
    if(m < R) update(L, R, v, m+1, r, o<<1|1);
    pushup(o);
}
int query(int L, int R, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) return sum[o];
    int ans = 0;
    if(L <= m) add(ans, query(L, R, l, m, o<<1));
    if(m < R) add(ans, query(L, R, m+1, r, o<<1|1));
    pushup(o);
    return ans;
}
int main() {
    while(~scanf("%d%d",&n,&h)) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            b[i-1] = a[i];
        }
        sort(b, b+n);
        int len = unique(b, b+n) - b;
        build(1, len, 1);
        int ans = 0;
        for(int i=1;i<=n;i++) {
            int l = lower_bound(b, b+len, a[i]-h) - b + 1;
            int r = upper_bound(b, b+len, a[i]+h) - b ;
            int pos = lower_bound(b, b+len, a[i]) - b + 1;
            d[i] = 1;
            add(d[i], query(l, r, 1, len, 1));
            add(ans, d[i]-1);
            update(pos, pos, d[i], 1, len, 1);
        }
        printf("%d\n",ans);
    }
    return 0;
}