HDU 3473

分析可知，最优的x应该在区间中的数排列后最中间的地方选择。由于区间的数个数有奇偶之分，于是当奇数个时，就是中位数了。偶数个时，就是排列后中间两数区间的任意一个。

可以应用划分树求得前半部分，树状数组统计。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
#define lowbit(x) (x&(-x))
using namespace std;

const int N=100050;
int sorted[N],n,m;
struct node{
    int val[N];
    int num[N];
    LL sum[N];
}tp[20];
LL ANS;
LL arrayTree[N];

void build(int lft,int rht,int p){
    if(lft==rht) return ;
    int i,mid=(lft+rht)/2;
    int isame=mid-lft+1,same=0;
    for(i=lft;i<=rht;i++){
        if(tp[p].val[i]<sorted[mid]) isame--;
    }
    int ln=lft,rn=mid+1;
    for(i = lft; i <= rht; i++) {
        if(i == lft) {
            tp[p].num[i] = 0;
            tp[p].sum[i]=0;
        } else {
            tp[p].num[i] = tp[p].num[i-1];
            tp[p].sum[i]=tp[p].sum[i-1];
        }
        if(tp[p].val[i] < sorted[mid]) {
            tp[p].num[i]++;
            tp[p].sum[i]+=tp[p].val[i];
            tp[p+1].val[ln++] = tp[p].val[i];
        }else if(tp[p].val[i] > sorted[mid]) {
            tp[p+1].val[rn++] = tp[p].val[i];
        }else {
            if(same < isame) {
                same++;
                tp[p].num[i]++;
                tp[p].sum[i]+=tp[p].val[i];
                tp[p+1].val[ln++] = tp[p].val[i];
            }else {
                tp[p+1].val[rn++] = tp[p].val[i];
            }
        }
    }
    build(lft, mid, p+1);
    build(mid+1, rht, p+1);
}
 
int query(int a, int b, int k, int p, int lft, int rht) {
    if(lft == rht) {
    	return tp[p].val[a];
    }
    LL sss=0;
    int s, ss, b2, bb, mid = (lft+rht)/2;
    if(a == lft) {
        s = tp[p].num[b];
        ss = 0;
        sss=tp[p].sum[b];
    } else {
        s = tp[p].num[b] - tp[p].num[a-1];
        ss = tp[p].num[a-1];
        sss=tp[p].sum[b]-tp[p].sum[a-1];
    }
    if(s >= k) {
        a = lft + ss;
        b = lft + ss + s - 1;
        return query(a, b, k, p+1, lft, mid);
    } else {
        bb = a - lft - ss;
        b2 = b - a + 1 - s;    
        a = mid + bb + 1;
        b = mid + bb + b2;
        ANS+=sss;
        return query(a, b, k-s,p+1, mid+1, rht);
    }
}

void update(int i,int w){
	for(int k=i;k<=n;k+=lowbit(k)){
		arrayTree[k]+=w;
	}
}

LL arraySum(int index){
	if(index==0) return 0;
	LL ret=0;
	for(int i=index;i>=1;i-=lowbit(i))
	ret+=arrayTree[i];
	return ret;
}

LL getsum(int l,int r){
//	cout<<arraySum(r)<<endl;
	return arraySum(r)-arraySum(l-1);
}

int main(){
	int T,Case=0;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(arrayTree,0,sizeof(arrayTree));
		for(int i=1;i<=n;i++){
			scanf("%d",&tp[0].val[i]);
			sorted[i]=tp[0].val[i];
			update(i,sorted[i]);
		}
		ANS=0;
		sort(sorted+1,sorted+1+n);
		build(1,n,0);
		scanf("%d",&m);
		int l,r;
		printf("Case #%d:
",++Case);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&l,&r);
			l++,r++;
			LL spre=getsum(l,r);
			ANS=0;
			if((r-l+1)%2==0){
				int mid=query(l,r,(r-l+1)/2+1,0,1,n);
				printf("%I64d
",spre-ANS-ANS);
			}
			else{
				int mid=query(l,r,(r-l+1)/2+1,0,1,n);
				printf("%I64d
",spre-ANS-ANS-mid);
			}
		}
		puts("");
	}
	return 0;
}