HDU 3473 Minimum Sum 【划分树】

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=3473

★没想到划分树里面也可以加东西，wcsl

---

题意：

给你一个由n个数组成的序列，有m次询问，每次询问给你一个区间（l，r）让你输出 x和这个区间的每一个数的差的绝对值 的求和 的最小值，x为任意数

---

思路：

这个x可以是排序后的区间的最居中的值：

我们把这个区间上的数想象为数轴上的点，当为奇数个时：
★这里的xn代表的是第n个点到x的距离
图很丑，将就一下嘛~ 黑圈和红圈分别代表区间的点 和 x值代表的点
上面是红圈在第三个点时的情况，下面是红圈在其它地方的情况（红线代表距离）

很清楚的看到，下面的红线距离比上面正好多了一个x3，所以当点数为奇数时x的值越靠近中间时 总值是越小的（可以多画几个试试，我数学不行 只会大概证明一下啦 ）
当为偶数个时同理，差不多， 不过x可以再中间两个点以及这两个点之间
但是为了统一奇数偶数的情况，我们不妨取题目已经给的点上

划分树：

设查询区间为（l，r），我们找其中第 ( r - l + 1 )/2+1 大的数当做x
那么我们通过划分树就可以找到x，但是怎么求最小值呢？

求最小值：

在区间里，作为中间值，x一定有ln个在它左边的数，rn个在它右边的数 ln+rn=y-x+1
如果我们知道，它左边的数的和sum1 和它右边的数的和sum2 那问题就简单了 sum1+sum2=sum[y]-sum[x-1]
即LL ans=ln*x-sum1+sum2-rn*x;
求ln和sum1的过程 要充分理解划分树的性质，我是看了半天的awa

---

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define r(x) read(x)
using namespace std;
typedef long long LL;
const int N=1e5+5;
const int M=1e3+5;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=acos(-1);
const double eps=1e-8;
template<class T>
inline void read(T &x)
{
    char c;x=1;
    while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
    T res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    x*=res;
}
LL sum[N];
LL ss[20][N];
int f[N];
int v[20][N];
int num[20][N];
LL sum1,sum2;
LL ln,rn;
void build(int l,int r,int dep)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    int res=(mid-l+1);
    for(int i=l;i<=r;i++) if(v[dep][i]<f[mid]) res--;
    int l1=l,l2=mid+1;
    for(int i=l;i<=r;i++){
        if(v[dep][i]<f[mid]){
            v[dep+1][l1++]=v[dep][i];
            ss[dep][i]=ss[dep][i-1]+v[dep][i];
        }
        else if(v[dep][i]==f[mid]&&res>0){
            v[dep+1][l1++]=v[dep][i];
            ss[dep][i]=ss[dep][i-1]+v[dep][i];
            res--;
        }
        else{
            v[dep+1][l2++]=v[dep][i];
            ss[dep][i]=ss[dep][i-1];
        }
        num[dep][i]=num[dep][l-1]+l1-l;
    }
    build(l,mid,dep+1);
    build(mid+1,r,dep+1);
}
int query(int l,int r,int dep,int x,int y,int k)
{
//    cout<<l<<' '<<r<<endl;
    if(x==y) return v[dep][x];
    int mid=(l+r)>>1;
    int cnt=num[dep][y]-num[dep][x-1];
    if(k<=cnt){
        int l1=l+num[dep][x-1]-num[dep][l-1];
        int r1=l1+cnt-1;
        return query(l,mid,dep+1,l1,r1,k);
    }
    else{
        sum1+=ss[dep][y]-ss[dep][x-1];
        ln+=num[dep][y]-num[dep][x-1];
        int r2=y+num[dep][r]-num[dep][y];
        int l2=r2-(y-x-cnt);
        return query(mid+1,r,dep+1,l2,r2,k-cnt);
    }
}
int main()
{
    int t; r(t);
    int cas=0;
    while(t--){
        int n,m;
        r(n);
        for(int i=1;i<=n;i++){
            r(f[i]);
            v[0][i]=f[i];
            sum[i]=sum[i-1]+f[i];
        }
        sort(f+1,f+n+1);
        build(1,n,0);
        r(m);
        printf("Case #%d:\n",++cas);
        while(m--){
            int a,b;
            r(a); r(b);
            a++; b++;
            sum1=sum2=0;
            ln=rn=0;
            int x=query(1,n,0,a,b,(b-a+1)/2+1);
            sum2=sum[b]-sum[a-1]-sum1;
            rn=b-a+1-ln;
            LL ans=ln*x-sum1+sum2-rn*x;
//            cout<<ln<<' '<<rn<<' '<<sum1<<' '<<sum2<<endl;
            cout<<ans<<endl;
        }
        cout<<endl;
    }
    return 0;
}