HDU 2227 Find the nondecreasing subsequences（線段樹+離散化+DP）

題目連結：點選打開連結

題意：給你n個數， 求非遞減子序列的個數。

思路：很容易想到， 用d[i]表示， 以a[i]為最後一個元素的非減子序列個數。  那麼每次轉移， 就是sum(d[j]) (其中 j < i && a[j] <= a[i]) ， 那麼這就變成了經典水題， 這個a[j] < a[i]的限制條件可放到線段樹下标上來維護， 那麼我們隻需要用線段樹來維護前面所有符合a[j] < a[i]的 d[j]的和就行了。

那麼最終答案是所有d[i] (1 <= i <= n)的和。

細節參見代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#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 = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m;
ll sum[maxn<<2], d[maxn],a[maxn],b[maxn];
inline void add(ll& a, ll 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);
}
ll query(int L, int R, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) return sum[o];
    ll 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));
    return ans;
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++) {
            scanf("%I64d",&a[i]);
            b[i-1] = a[i];
        }
        sort(b, b+n);
        int len = unique(b, b+n) - b;
        build(1, len, 1);
        for(int i=1;i<=n;i++) {
            int r = lower_bound(b, b+len, a[i]) - b + 1;
            ll cur = query(1, r, 1, len, 1);
            d[i] = 1;
            add(d[i], cur);
            update(r, r, d[i], 1, len, 1);
        }
        printf("%I64d\n",query(1, len, 1, len, 1));
    }
    return 0;
}