1 //Accepted    28904 KB    781 ms  2 //划分树  3 //所求x即为l，r区间排序后的中位数t  4 //然后求出小于t的数的和sum1，这个可以用划分树做  5 //求出整个区间的和sum，可以用O(1)的数组做  6 //ans=(k-1)*t-sum1+sum-sum1-(l-r+1-k+1)*t  7 #include <cstdio>  8 #include <cstring>  9 #include <iostream> 10 #include <queue> 11 #include <cmath> 12 #include <algorithm> 13 using namespace std; 14 /** 15   * This is a documentation comment block 16   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 17   * @authr songt 18   */ 19 const int imax_n = 100005; 20 struct node 21 { 22     int val[imax_n]; 23     int num[imax_n]; 24     __int64 sum[imax_n]; 25 }f[20]; 26  27 int a[imax_n]; 28 __int64 all[imax_n]; 29 int sorted[imax_n]; 30 int n; 31  32 void build(int t,int l,int r) 33 { 34     if (l==r) return ; 35     int mid=(l+r)/2; 36     int isame=mid-l+1; 37     int same=0; 38     for (int i=l;i<=r;i++) 39     { 40         if (f[t].val[i]<sorted[mid]) isame--; 41     } 42     int ln=l; 43     int rn=mid+1; 44     for (int i=l;i<=r;i++) 45     { 46         if (i==l) 47         { 48             f[t].num[i]=0; 49             f[t].sum[i]=0; 50         } 51         else 52         { 53             f[t].sum[i]=f[t].sum[i-1]; 54             f[t].num[i]=f[t].num[i-1]; 55         } 56  57         if (f[t].val[i]<sorted[mid]) 58         { 59             f[t].num[i]++; 60             f[t].sum[i]+=f[t].val[i]; 61             f[t+1].val[ln++]=f[t].val[i]; 62         } 63         else if (f[t].val[i]>sorted[mid]) 64         { 65             f[t+1].val[rn++]=f[t].val[i]; 66         } 67         else 68         { 69             if (same<isame) 70             { 71                 same++; 72                 f[t].num[i]++; 73                 f[t].sum[i]+=f[t].val[i]; 74                 f[t+1].val[ln++]=f[t].val[i]; 75             } 76             else 77             { 78                 f[t+1].val[rn++]=f[t].val[i]; 79             } 80         } 81     } 82     build(t+1,l,mid); 83     build(t+1,mid+1,r); 84 } 85 __int64 sum=0; 86 int lnum; 87 int query(int t,int l,int r,int a,int b,int k) 88 { 89     int s,ss; 90     if (l==r) return f[t].val[l]; 91     int mid=(l+r)/2; 92     __int64 tsum=0; 93     if (a==l) 94     { 95         ss=0; 96         s=f[t].num[b]; 97         tsum=f[t].sum[b]; 98     } 99     else100     {101         ss=f[t].num[a-1];102         s=f[t].num[b]-ss;103         tsum=f[t].sum[b]-f[t].sum[a-1];104     }105     if (s>=k)106     {107         a=l+ss;108         b=l+ss+s-1;109         return query(t+1,l,mid,a,b,k);110     }111     else112     {113         //lnum+=s;114         int b1=a-l-ss;115         int b2=b-a+1-s;116         a=mid+1+b1;117         b=mid+b1+b2;118         sum+=tsum;119         return query(t+1,mid+1,r,a,b,k-s);120     }121 }122 int Q;123 int x,y;124 void slove()125 {126     build(0,1,n);127     scanf("%d",&Q);128     for (int i=1;i<=Q;i++)129     {130         scanf("%d%d",&x,&y);131         x++;132         y++;133         __int64 sum1=all[y]-all[x-1];134         //printf("sum1=%I64d\n",sum1);135         sum=0;136         //lnum=0;137         //printf("sum=%I64d\n",sum);138         int k=(x+y)/2-x+1;139         int t=query(0,1,n,x,y,k);140         //printf("t=%d\n",t);141         lnum=k-1;142         __int64 ans=-sum+sum1-sum-(__int64 )(y-x+1-lnum-lnum)*t;143         printf("%I64d\n",ans);144     }145 }146 int main()147 {148     int T;149     int t=0;150     scanf("%d",&T);151     while (T--)152     {153         scanf("%d",&n);154         all[0]=0;155         for (int i=1;i<=n;i++)156         {157             scanf("%d",&a[i]);158             f[0].val[i]=sorted[i]=a[i];159             all[i]=all[i-1]+a[i];160         }161         printf("Case #%d:\n",++t);162         sort(sorted+1,sorted+n+1);163         slove();164         printf("\n");165     }166     return 0;167 }