//Accepted 28904 KB 781 ms //划分树 //所求x即为l,r区间排序后的中位数t //然后求出小于t的数的和sum1,这个可以用划分树做 //求出整个区间的和sum,可以用O(1)的数组做 //ans=(k-1)*t-sum1+sum-sum1-(l-r+1-k+1)*t #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> using namespace std; /** * This is a documentation comment block * 如果有一天你坚持不下去了,就想想你为什么走到这儿! * @authr songt */ ; struct node { int val[imax_n]; int num[imax_n]; __int64 sum[imax_n]; }f[]; int a[imax_n]; __int64 all[imax_n]; int sorted[imax_n]; int n; void build(int t,int l,int r) { if (l==r) return ; ; ; ; for (int i=l;i<=r;i++) { if (f[t].val[i]<sorted[mid]) isame--; } int ln=l; ; for (int i=l;i<=r;i++) { if (i==l) { f[t].num[i]=; f[t].sum[i]=; } else { f[t].sum[i]=f[t].sum[i-]; f[t].num[i]=f[t].num[i-]; } if (f[t].val[i]<sorted[mid]) { f[t].num[i]++; f[t].sum[i]+=f[t].val[i]; f[t+].val[ln++]=f[t].val[i]; } else if (f[t].val[i]>sorted[mid]) { f[t+].val[rn++]=f[t].val[i]; } else { if (same<isame) { same++; f[t].num[i]++; f[t].sum[i]+=f[t].val[i]; f[t+].val[ln++]=f[t].val[i]; } else { f[t+].val[rn++]=f[t].val[i]; } } } build(t+,l,mid); build(t+,mid+,r); } __int64 sum=; int lnum; int query(int t,int l,int r,int a,int b,int k) { int s,ss; if (l==r) return f[t].val[l]; ; __int64 tsum=; if (a==l) { ss=; s=f[t].num[b]; tsum=f[t].sum[b]; } else { ss=f[t].num[a-]; s=f[t].num[b]-ss; tsum=f[t].sum[b]-f[t].sum[a-]; } if (s>=k) { a=l+ss; b=l+ss+s-; ,l,mid,a,b,k); } else { //lnum+=s; int b1=a-l-ss; -s; a=mid++b1; b=mid+b1+b2; sum+=tsum; ,mid+,r,a,b,k-s); } } int Q; int x,y; void slove() { build(,,n); scanf("%d",&Q); ;i<=Q;i++) { scanf("%d%d",&x,&y); x++; y++; __int64 sum1=all[y]-all[x-]; //printf("sum1=%I64d\n",sum1); sum=; //lnum=0; //printf("sum=%I64d\n",sum); -x+; ,,n,x,y,k); //printf("t=%d\n",t); lnum=k-; __int64 ans=-sum+sum1-sum-(__int64 )(y-x+-lnum-lnum)*t; printf("%I64d\n",ans); } } int main() { int T; ; scanf("%d",&T); while (T--) { scanf("%d",&n); all[]=; ;i<=n;i++) { scanf("%d",&a[i]); f[].val[i]=sorted[i]=a[i]; all[i]=all[i-]+a[i]; } printf("Case #%d:\n",++t); sort(sorted+,sorted+n+); slove(); printf("\n"); } ; }