1 //Accepted    7552 KB    844 ms  2 //dp[i]=sum(dp[j])+1 j<i && a[j]<a[i]  3 //可以用线段树求所用小于a[i]的dp[j]的和  4 //需要离散化  5 #include <cstdio>  6 #include <cstring>  7 #include <iostream>  8 #include <queue>  9 #include <cmath> 10 #include <algorithm> 11 using namespace std; 12 /** 13   * This is a documentation comment block 14   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 15   * @authr songt 16   */ 17 const int imax_n = 100005; 18 const int pp= 1000000007; 19 struct node 20 { 21     int l,r; 22     long long sum; 23 }f[imax_n*3]; 24 void build(int t,int l,int r) 25 { 26     f[t].l=l; 27     f[t].r=r; 28     f[t].sum=0; 29     if (l==r) 30     { 31         return ; 32     } 33     int mid=(l+r)/2; 34     build(2*t,l,mid); 35     build(2*t+1,mid+1,r); 36 } 37 long long query(int t,int l,int r) 38 { 39     if (f[t].l==l && f[t].r==r) 40     { 41         return f[t].sum%pp; 42     } 43     int mid=(f[t].l+f[t].r)/2; 44     if (r<=mid) return query(2*t,l,r)%pp; 45     else 46     { 47         if (l>mid) return query(2*t+1,l,r)%pp; 48         else return (query(2*t,l,mid)+query(2*t+1,mid+1,r))%pp; 49     } 50 } 51 void update(int t,int l,int r,int c) 52 { 53     if (f[t].l==l && f[t].r==r) 54     { 55         f[t].sum=(f[t].sum+(r-l+1)*c%pp)%pp; 56         return ; 57     } 58     f[t].sum=(f[t].sum+(r-l+1)*c%pp)%pp; 59     int mid=(f[t].l+f[t].r)/2; 60     if (r<=mid) update(2*t,l,r,c); 61     else 62     { 63         if (l>mid) update(2*t+1,l,r,c); 64         else 65         { 66             update(2*t,l,mid,c); 67             update(2*t+1,mid+1,r,c); 68         } 69     } 70     //f[t].sum=(f[2*t].sum+f[2*t+1].sum)%pp; 71 } 72 int n; 73 struct anode 74 { 75     int a,b; 76     int tid; 77 }a[imax_n]; 78 int cmp(anode x,anode y) 79 { 80     return x.a<y.a; 81 } 82 int cmp2(anode x,anode y) 83 { 84     return x.tid<y.tid; 85 } 86 void pre() 87 { 88     sort(a+1,a+n+1,cmp); 89     int k=2; 90     a[1].b=2; 91     int i=2; 92     while (i<=n) 93     { 94         if (a[i].a==a[i-1].a) 95         { 96             a[i].b=k; 97         } 98         else 99         {100             a[i].b=k+1;101             k++;102         }103         i++;104     }105     sort(a+1,a+n+1,cmp2);106    // for (int i=1;i<=n;i++)107    // {108    //     printf("%d ",a[i].b);109    // }110     //printf("\n");111 }112 void slove()113 {114     long long ans=0;115     build(1,1,n+2);116     pre();117     for (int i=1;i<=n;i++)118     {119         int t=query(1,1,a[i].b-1)%pp;120         t++;121         ans=(ans+t)%pp;122         update(1,a[i].b,a[i].b,t);123     }124     printf("%lld\n",ans);125 }126 int main()127 {128     //printf("%d\n",2*pp);129     int T;130     scanf("%d",&T);131     for (int t=1;t<=T;t++)132     {133         scanf("%d",&n);134         for (int i=1;i<=n;i++)135         {136             scanf("%d",&a[i].a);137             a[i].tid=i;138         }139         printf("Case %d: ",t);140         slove();141     }142     return 0;143 }