求序列的非降子序列個數模 1,000,000,007。n ≤ 100,000，元素值 ≤ 2^31。
dp[i] = 以第 i 個元素結尾的非降子序列數。
dp[i] = 1 + Σ_{j
直接雙循環 O(n²) 超時。離散化數值後，用樹狀數組維护前綴和：
遍歷 i，查詢 ≤ a[i] 的 dp 和，加 1 得 dp[i]，再更新 BIT。
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 100010;
int n, a[MAXN], sorted[MAXN], bit[MAXN];
long long dp[MAXN];
int lowbit(int x) { return x & -x; }
void add(int idx, long long val) {
for (; idx <= n; idx += lowbit(idx)) {
bit[idx] = (bit[idx] + val) % MOD;
}
}
long long query(int idx) {
long long res = 0;
for (; idx > 0; idx -= lowbit(idx))
res = (res + bit[idx]) % MOD;
return res;
}
int main() {
while (scanf("%d", &n) == 1) {
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sorted[i] = a[i];
}
sort(sorted+1, sorted+n+1);
int m = unique(sorted+1, sorted+n+1) - sorted - 1;
memset(bit, 0, sizeof(bit));
long long ans = 0;
for (int i = 1; i <= n; i++) {
int idx = lower_bound(sorted+1, sorted+m+1, a[i]) - sorted;
long long sum = query(idx);
dp[i] = (sum + 1) % MOD;
add(idx, dp[i]);
ans = (ans + dp[i]) % MOD;
}
printf("%lld\n", ans);
}
return 0;
}
