http://acm.hdu.edu.cn/showproblem.php?pid=2227
用dp[i]表示以第i个数为结尾的nondecreasing串有多少个。
那么对于每个a[i]
要去找 <= a[i]的数字那些位置，加上他们的dp值即可。
可以用树状数组维护
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int MOD = 1000000007; const int maxn = 100000 + 20; LL a[maxn], b[maxn]; int n; LL c[maxn]; LL lowbit(LL x) {return x & (-x); } void UpDate(int pos, LL val) {while (pos <= n) {c[pos] += val;if (c[pos] >= MOD) c[pos] %= MOD;pos += lowbit(pos);} } LL query(int pos) {LL ans = 0;assert(pos >= 0);while (pos) {ans += c[pos];pos -= lowbit(pos);}return ans; } void work() {memset(c, 0, sizeof c);for (int i = 1; i <= n; ++i) {cin >> a[i];b[i] = a[i];}sort(b + 1, b + 1 + n);LL ans = 0;for (int i = 1; i <= n; ++i) {int pos = lower_bound(b + 1, b + 1 + n, a[i]) - b;LL tans = query(pos) + 1;ans += tans;if (ans >= MOD) ans %= MOD;UpDate(pos, tans);}cout << ans << endl; }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifIOS;while (cin >> n) work();return 0; }