题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1085
题意：
问你有多少个上升子序列。
思路：
dp[i]表示以第i个数结尾的上升序列数量。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <map> 6 using namespace std; 7 typedef long long LL; 8 const int N = 1e5 + 5; 9 int a[N]; 10 int b[N], n; 11 LL bit[N], mod = 1e9 + 7; 12 LL dp[N]; 13 14 void add(int i, LL val) { 15 for( ; i <= n; i += (i&-i)) 16 bit[i] += val; 17 } 18 19 LL sum(int i) { 20 LL s = 0; 21 for( ; i >= 1; i -= (i&-i)) 22 s += bit[i]; 23 return s; 24 } 25 26 int main() 27 { 28 int t; 29 scanf("%d", &t); 30 for(int ca = 1; ca <= t; ++ca) { 31 scanf("%d", &n); 32 for(int i = 1; i <= n; ++i) { 33 scanf("%d", a + i); 34 b[i] = a[i]; 35 } 36 sort(b + 1, b + n + 1); 37 memset(bit, 0, sizeof(bit)); 38 memset(dp, 0, sizeof(dp)); 39 for(int i = 1; i <= n; ++i) { 40 a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b; 41 dp[i]++; 42 } 43 for(int i = 1; i <= n; ++i) { 44 dp[i] += sum(a[i] - 1); 45 dp[i] %= mod; 46 add(a[i], dp[i]); 47 } 48 LL ans = 0; 49 for(int i = 1; i <= n; ++i) { 50 ans += dp[i]; 51 ans %= mod; 52 } 53 printf("Case %d: %lld\n", ca, ans); 54 } 55 return 0; 56 }