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);    }}