题意：在区间中找一个数，求出该区间每个数与这个数距离的总和，使其最小
找的数字是中位数（若是偶数个，则中间随便哪个都可）接着找到该区间比此数大的数的总和
区间中位数可以使用划分树，然后在其中记录：每层的 1-i 中划分到左区间的总和
划分树：
划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值 。
划分树和归并树都是用线段树作为辅助的，原理是基于快排 和归并排序 的。
划分树的建树过程基本就是模拟快排过程，取一个已经排过序的区间中值，然后把小于中值的点放左边，大于的放右边。并且记录d层第i个数之前（包括i）小于中值的放在左边的数。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define dir(a,b) (a>>b) const int Max=1e5+7; int orval[Max]; int dsegtr[20][Max];//记录第i层划分树的序列 int lele[20][Max];//记录第i层的1-i划分到左子树的元素个数（包括i） long long sum[20][Max],psum[Max],lsum;//每层的1-i中划分到左区间的总和 void Create(int sta,int enn,int cur) { int mid=dir(sta+enn,1); int lsame=mid-sta+1;//此区间左边不小于orval[mid]的个数 int lsta=sta,rsta=mid+1; for(int i=sta; i<=mid; ++i) { if(orval[i]<orval[mid]) lsame--; } for(int i=sta; i<=enn; ++i)//给下一层赋值 { sum[cur][i]=sum[cur][i-1]; if(i==sta) { lele[cur][i]=0;//表示[l, i]内有多少个数分到左边 } else { lele[cur][i]=lele[cur][i-1]; } if(dsegtr[cur][i]==orval[mid]) { if(lsame) { sum[cur][i]+=dsegtr[cur][i]; lsame--; lele[cur][i]++; dsegtr[cur+1][lsta++]=dsegtr[cur][i];//相当于移动元素到左边 } else { dsegtr[cur+1][rsta++]=dsegtr[cur][i];//相当于移动元素到右边 } } else if(dsegtr[cur][i]<orval[mid]) { sum[cur][i]+=dsegtr[cur][i]; lele[cur][i]++; dsegtr[cur+1][lsta++]=dsegtr[cur][i]; } else { dsegtr[cur+1][rsta++]=dsegtr[cur][i]; } } if(sta==enn) return; Create(sta,mid,cur+1); Create(mid+1,enn,cur+1); return; } int Query(int sta,int enn,int cur,int lef,int rig,int k) { int lsame;//[sta, lef)内将被划分到左子树的元素数目 int rsame;//[lef,rig]内将被划分到左子树的元素数目 关键 int mid=dir(sta+enn,1); if(sta==enn) return dsegtr[cur][sta]; if(sta==lef)//特判 { lsame=0; rsame=lele[cur][rig]; } else { lsame=lele[cur][lef-1]; rsame=lele[cur][rig]-lsame; } if(k<=rsame) { return Query(sta,mid,cur+1,sta+lsame,sta+lsame+rsame-1,k);//关键 } else { lsum+=sum[cur][rig]-sum[cur][lef-1];//所求值不在左区间 return Query(mid+1,enn,cur+1,mid-sta+1+lef-lsame,mid-sta+1+rig-lsame-rsame,k-rsame);//关键 } } long long Solve(long long temp,int rig,int lef,int k) { long long resr=psum[rig]-psum[lef-1]-lsum-temp-(long long)(rig-lef+1-k)*temp; long long resl=(long long)(k-1)*temp-lsum; return resr+resl; } int main() { int n,m,t,coun=0; int lef,rig; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<20;++i) sum[i][0]=0ll; psum[0]=0ll; for(int i=1; i<=n; ++i) { scanf("%d",&orval[i]); psum[i]=psum[i-1]+orval[i]; dsegtr[0][i]=orval[i]; sum[0][i]=sum[0][i-1]+orval[i]; } sort(orval+1,orval+n+1); Create(1,n,0); scanf("%d",&m); printf("Case #%d: ",++coun); for(int i=0; i<m; ++i) { lsum=0ll; scanf("%d %d",&lef,&rig); lef++,rig++; int temp=Query(1,n,0,lef,rig,(rig-lef+2>>1)); printf("%I64d ",Solve(temp,rig,lef,(rig-lef+2>>1))); } printf(" "); } return 0; }
参考：http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html