Lightoj 1085 All Possible Increasing Subsequences

http://lightoj.com/volume_showproblem.php?problem=1085

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define N 100005
4. #define MOD 1000000007
5. int a[N], b[N];
6. int tree[N];
7. int query(int idx){
8.        long long  sum=0;
9.        while(idx>0){
10.              sum+=tree[idx];
11.              sum%=MOD;
12.              idx -= idx & (-idx);
13.        }
14.        return (int) sum%MOD;
15. }
16. void update(int idx, int x, int n) //n is the size of the array, x is the number to add
17. {
18.        while(idx<=n){
19.              tree[idx]+=x;
20.              tree[idx]%=MOD;
21.              idx += idx & (-idx);
22.        }
23. }
25. int main(){
26.     int ts;
27.     scanf("%d", &ts);
28.     for(int p = 1; p <= ts; p++){
29.     memset(tree, 0, sizeof(tree));
30.     int n;
31.     scanf("%d", &n);
32.     for(int i = 0; i <n; i++){
33.         scanf("%d", &a[i]);
34.         b[i] = a[i];
35.     }
36.     map<int, int>mp;
37.     sort(b, b+n);
38.     int cnt = 2;
39.     mp[b[0]] = 1;
40.     for(int i = 1; i <n; i++){
41.         if(b[i] != b[i-1]){
42.             mp[b[i]] = cnt;
43.             cnt++;
44.         }
45.     }
46.     for(int i = 0; i <n; i++){
47.         update(mp[a[i]], (query(mp[a[i]]-1)+1)%MOD,n);
48.        
49.        
50.     }
51.     printf("Case %d: %d\n",p,query(n)%MOD);
52.     }
53.     return 0;
55. }