hdu 3473 Minimum Sum

题意：给你一个区间[l,r],要求sum(x-xi)(l<=i<=r)的最小值,其中x必须为xl,xl+1...xr中的一个数

当x为[l,r]的中位数的时候，满足要求。求任意区间的中位数可以用划分树（k-number）来解决，同样的，我们用suml[d][i]来记录划分树中第d层到数i位置放入左子树的数字的和，

具体见代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 #define MAXN 100010
  8 
  9 long sorted[MAXN];
 10 long toLeft[30][MAXN],val[30][MAXN];
 11 __int64 lsum[30][MAXN],sum[MAXN];//lsum[d][i]为第d层到第xi被划入左子树的数字的和，sum[i]为1到i的和
 12 __int64 lnum,rnum,suml,sumr,ans;
 13 
 14 void build(int d,int l,int r)//建树
 15 {
 16     if(l==r)return;
 17     int m = (l+r)>>1;
 18     int i;
 19     int same = m-l+1;//位于左子树的数据
 20     for(i=l;i<=r;i++)  //计算放于左子树中与中位数相等的数字个数
 21         if(val[d][i]<sorted[m])
 22             same--;
 23     int ls = l;
 24     int rs = m+1;
 25     for(i=l;i<=r;i++)
 26     {
 27         int flag = 0;
 28         if((val[d][i]<sorted[m])||(val[d][i]==sorted[m]&&same>0))//放入左子树
 29         {
 30             flag = 1;
 31             val[d+1][ls++] = val[d][i];
 32             if(val[d][i]==sorted[m])same--;
 33             lsum[d][i]=lsum[d][i-1]+val[d][i];
 34         }
 35         else//右子树
 36         {
 37             val[d+1][rs++] = val[d][i];
 38             lsum[d][i]=lsum[d][i-1];
 39         }
 40         toLeft[d][i]=toLeft[d][i-1]+flag;
 41     }
 42     build(d+1,l,m);
 43     build(d+1,m+1,r);
 44 }
 45 int query(int L,int R,int k,int d,int l,int r)
 46 {
 47     if(L==R)return val[d][L];
 48     int m = (l+r)>>1;
 49     int x = toLeft[d][L-1]-toLeft[d][l-1];//位于L左边的放于左子树中的数字个数
 50     int y = toLeft[d][R] - toLeft[d][l-1];//到R为止位于左子树的个数
 51     int ry = R-l-y;//到right右边为止位于右子树的数字个数
 52     int cnt = y-x;//[left,right]区间内放到左子树中的个数
 53     int rx = L-l-x;//left左边放在右子树中的数字个数
 54     if(cnt>=k)
 55         return query(l+x,l+y-1,k,d+1,l,m);
 56     else
 57     {
 58         lnum=lnum+cnt;
 59         suml=suml+lsum[d][R]-lsum[d][L-1];
 60         return query(m+rx+1,m+1+ry,k-cnt,d+1,m+1,r);
 61     }
 62 }
 63 
 64 int main()
 65 {
 66     int n,m,t;
 67     scanf("%d",&t);
 68     int cas=1;
 69     while(t--)
 70     {
 71            scanf("%d",&n);
 72         sum[0]=0;
 73            for(int i=1;i<=n;i++)
 74         {
 75             scanf("%d",&val[0][i]);
 76             sorted[i]=val[0][i];
 77             sum[i]=sum[i-1]+sorted[i];
 78            }
 79         scanf("%d",&m);
 80            sort(sorted+1,sorted+n+1);
 81            build(0,1,n);
 82         printf("Case #%d:\n",cas++);
 83         while(m--)
 84         {
 85              int l,r,k;
 86                scanf("%d%d",&l,&r);
 87              l++,r++;
 88              k=((r-l)/2)+1;
 89              suml=0;
 90              lnum=0;
 91              int ave = query(l,r,k,0,1,n);
 92              rnum=(r-l+1-lnum);
 93              sumr=sum[r]-sum[l-1]-suml;
 94              ans=sumr-ave*(rnum-lnum)-suml;
 95                 printf("%I64d\n",ans);
 96            }
 97         printf("\n");
 98     }
 99     return 0;
100 }