hdu 3473 划分树
题目大意：有一个数列 x1..xn,要求一个数x使得 sigma(abs(xi-x))值最小，很明显，对数列进行排序后最中间的那个数就是x，可用划分树求得，那么如何求和呢，经过计算可知，既然
x 是最中间的那个数，那么最后的和 即为 x左边 xmid-x1+xmid-x2.. + x(mid+1) - xmid + x(mid+2)-xmid.. 整理得 xmid*(lefnum-rignum)+rigsum-lefsum
lefnum为划分过程进入左子树的个数，lefsum为进入左子树的数之和
lefsum求法：在划分过程，当该层 有数进入左子树即 加上 该数，具体见代码。。
#include<iostream>#include<cstdio>#include<cstring>#include<math.h>#include<algorithm>using namespace std;#define MAXN 100010#define lson u<<1#define rson u<<1|1#define LL long longint sorted[MAXN],val[20][MAXN],Lnum[20][MAXN];LL sum[MAXN]={0},Lsum[20][MAXN],lefsum;int n,q,lefnum;struct Node{ int lef,rig,mid;}T[MAXN<<2];void Build(int u,int l,int r,int d){ T[u].lef=l; T[u].rig=r; T[u].mid=(l+r)>>1; if(l==r)return; int mid=T[u].mid; int lsame=mid-l+1; for(int i=l;i<=r;i++){ if(val[d][i]<sorted[mid])lsame--; } int p=T[u].lef,q=T[u].mid+1,same=0; Lsum[d][0]=0; for(int i=l;i<=r;i++){ if(i==l)Lnum[d][i]=0; else Lnum[d][i]=Lnum[d][i-1]; Lsum[d][i]=Lsum[d][i-1]; if(val[d][i]<sorted[mid]){ val[d+1][p++]=val[d][i]; Lsum[d][i]+=val[d][i]; Lnum[d][i]++; } else if(val[d][i]>sorted[mid]){ val[d+1][q++]=val[d][i]; } else { if(same<lsame){ val[d+1][p++]=val[d][i]; Lsum[d][i]+=val[d][i]; Lnum[d][i]++; same++; } else val[d+1][q++]=val[d][i]; } } Build(lson,l,mid,d+1); Build(rson,mid+1,r,d+1);}int Query(int u,int l,int r,int d,int k){ if(l==r)return val[d][l]; else { int n1,n2; if(l==T[u].lef){n1=0;n2=Lnum[d][r];} else {n1=Lnum[d][l-1];n2=Lnum[d][r]-n1;} if(n2>=k){ int newl=T[u].lef+n1; int newr=T[u].lef+n1+n2-1; return Query(lson,newl,newr,d+1,k); } else { lefnum+=n2; lefsum+=(LL)(Lsum[d][r]-Lsum[d][l-1]); //printf("lefsum:%lld\n",lefsum); int newl=T[u].mid+1+(l-T[u].lef-n1); int newr=newl+(r-l+1-n2)-1; return Query(rson,newl,newr,d+1,k-n2); } }}int main(){ int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&val[0][i]); sorted[i]=val[0][i]; sum[i]=sum[i-1]+val[0][i]; } sort(sorted+1,sorted+1+n); //memset(Lsum,0,sizeof(Lsum)); Build(1,1,n,0); int l,r; scanf("%d",&q); printf("Case #%d:\n",cas); while(q--){ scanf("%d%d",&l,&r); l++;r++; int k=(r-l+2)>>1; lefnum=lefsum=0; int midval=Query(1,l,r,0,k); //printf("midval %d\n",midval); printf("%I64d\n",(LL)midval*(lefnum-(r-l+1-lefnum))+sum[r]-sum[l-1]-lefsum-lefsum); //printf("lnum%d,rnum%d,lsum%lld,rsum%lld\n",lefnum,(r-l+1-lefnum),lefsum,sum[r]-sum[l-1]-lefsum); } putchar(10); }}