HDU-3743 Minimum Sum,划分树模板

被这个题坑了一下午，原来只需找一个最中间的数即可，我以为是平均数。

题意：找一个数使得这个数和区间内所有数的差的绝对值最小。输出最小值。

开始用线段树来了一发果断T了，然后各种优化依然T不断。于是只能用划分树做。不过，其实熟悉划分树也是模板水题。

打一个前缀和，然后这个数肯定是这个区间从大到小排在最中间的。所以查询一遍将小于中间这个数的和加起来，然后得到将小于这个数的个数。分为前半段和后半段分别加起来即可。

手残将一个地方写错了，然后无限RE。。。。最后一行一行debug，心塞。

ll sum[N],lsum[20][N];

int  tree[20][N],a[N],t_l[20][N];

void build(int l,int r,int id)

{

    if(l==r) return ;

    int mid=(l+r)/2;

    int same=mid-l+1;

    for(int i=l;i<=r;i++) if(tree[id][i]<a[mid]) same--;

    int lp=l,rp=mid+1;

for(int i=l;i<=r;i++)

    {

        if(tree[id][i]<a[mid])

        {

            tree[id+1][lp++]=tree[id][i];

            lsum[id][i]=lsum[id][i-1]+tree[id][i];

        }

        else if(tree[id][i]==a[mid]&&same>0)

        {

            tree[id+1][lp++]=tree[id][i],same--;

            lsum[id][i]=lsum[id][i-1]+tree[id][i];

        }

        else

        {

            tree[id+1][rp++]=tree[id][i];

            lsum[id][i]=lsum[id][i-1];

        }

        t_l[id][i]=t_l[id][l-1]+lp-l;

    }

    build(l,mid,id+1);

    build(mid+1,r,id+1);

}

ll isum;

int num;

int find(int l,int r,int k,int L,int R,int id)

{

    if(l==r) return tree[id][l];

    int mid=(L+R)/2;

    int cnt=t_l[id][r]-t_l[id][l-1];

    if(cnt>=k)

    {

        int newl=L+t_l[id][l-1]-t_l[id][L-1];

        int newr=newl+cnt-1;

        return  find(newl,newr,k,L,mid,id+1);

    }

    else

    {

        num+=cnt;

        isum+=lsum[id][r]-lsum[id][l-1];

        int newr=r+t_l[id][R]-t_l[id][r];

        int newl=newr-(r-l-cnt);

       return  find(newl,newr,k-cnt,mid+1,R,id+1);

    }

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    int t1=t;

    while(t--)

    {

        scanf("%d",&n);

        memset(sum,0,sizeof(sum));

       for(int i=0; i<20; i++) tree[i][0]=t_l[i][0]=lsum[i][0]=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&tree[0][i]);

            a[i]=tree[0][i];

            sum[i]=sum[i-1]+a[i];

        }

        sort(a+1,a+n+1);

        build(1,n,0);

        scanf("%d",&m);

        printf("Case #%d:\n",t1-t);

        while(m--)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            if(l==r) puts("0");

            else

            {

                l++,r++;

                int k=(r-l)/2+1;

                num=0;//得到小于中间这个数的个数

                isum=0;//得到小于中间这个数的和

                ll x=find(l,r,k,1,n,0);

                printf("%I64d\n",(ll)x*(num-(r-l+1-num))+sum[r]-sum[l-1]-isum-isum);

            }

        }

        puts("");

    }

    return 0;

}

注意 long long 。

巴特西

HDU-3743 Minimum Sum,划分树模板

最新文章

热门文章