hdu 3473 裸的划分树

时间：2022-01-22 15:08:50

思路：

用Sum[dep][i]记录从tree[po].l到i中进入左子树的和。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define Maxn 100010

#define inf 0x7fffffff

#define lowbit(x) (x&(-x))

#define lson(x) (x<<1)

#define rson(x) ((x<<1)|1)

#define mid ((tree[po].l+tree[po].r)>>1)

using namespace std;

struct Tree{

    int l,r;

}tree[Maxn*];

__int64 Sum[][Maxn],sum[Maxn];

__int64 lnum,lsum;

int sorted[Maxn];

int val[][Maxn],toLeft[][Maxn],n;

void BuildTree(int l,int r,int dep,int po)

{

    tree[po].l=l,tree[po].r=r;

    if(l==r) return ;

    int same=mid-l+,i;

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

        if(val[dep][i]<sorted[mid])

            same--;

    int lpos=l,rpos=mid+;

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

    {

        if(i==l)

            toLeft[dep][i]=;

        else

            toLeft[dep][i]=toLeft[dep][i-];

        Sum[dep][i]=Sum[dep][i-];

        if(val[dep][i]<sorted[mid])

           Sum[dep][i]+=(__int64)val[dep][i],toLeft[dep][i]++,val[dep+][lpos++]=val[dep][i];

        else

            if(val[dep][i]>sorted[mid])

            val[dep+][rpos++]=val[dep][i];

        else

            if(same)

            Sum[dep][i]+=(__int64)val[dep][i],toLeft[dep][i]++,val[dep+][lpos++]=val[dep][i],same--;

            else

            val[dep+][rpos++]=val[dep][i];

    }

    BuildTree(l,mid,dep+,lson(po));

    BuildTree(mid+,r,dep+,rson(po));

}

int query(int l,int r,int k,int dep,int po)

{

    if(l==r)

        return val[dep][l];

    int vd,invd;

    if(l==tree[po].l)

        vd=toLeft[dep][r],invd=;

    else

        vd=toLeft[dep][r]-toLeft[dep][l-],invd=toLeft[dep][l-];

    if(vd>=k){

        int newl=tree[po].l+invd;

        int newr=tree[po].l+vd+invd-;

        return query(newl,newr,k,dep+,lson(po));

    }

    else{

        int ss=l-tree[po].l-invd;

        int s=r-l+-vd;

        int newl=mid+ss+;

        int newr=mid+ss+s;

        lnum+=vd;

        lsum+=Sum[dep][r]-Sum[dep][l-];

        return query(newl,newr,k-vd,dep+,rson(po));

    }

}

int main()

{

    int m,i,j,k,s,t,T,Case=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

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

        {

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

            sorted[i]=val[][i];

            sum[i]=sum[i-]+(__int64)val[][i];

        }

        sort(sorted+,sorted++n);

        BuildTree(,n,,);

        __int64 temp;

        __int64 ans=;

        scanf("%d",&m);

        printf("Case #%d:\n",++Case);

        for(i=;i<=m;i++)

        {

            scanf("%d%d",&s,&t);

            s++,t++;

            lnum=lsum=;

            k=(t-s+)/;

            temp=(__int64)query(s,t,k,,);

            //cout<<lnum<<" "<<temp<<" "<<lsum<<" "<<sum[t]<<" "<<k<<" "<<sum[s-1]<<endl;

            ans=lnum*temp-lsum+sum[t]-sum[s-]-lsum-(t-s+-k)*temp;

            printf("%I64d\n",ans);

        }

        printf("\n");

    }

    return ;

}

相关文章