题目链接：HDU3473

【分析】首先可以确定要求的x肯定是区间[x,y]的中位数a[mid]，然后答案就是mid左边加右边的差值：(a[mid]-a[x])+(a[mid]-a[x+1])+(a[mid]-a[x+2])+…+a[mid]+(a[mid+1]-a[mid])+(a[mid+2]-a[mid]);化简后为：a[mid]*(lnum-rnum)+rsum-lsum;其中lnum是mid左边的数字个数，rnum是>=mid的个数，lsum是mid左边数字之和，rsum是右边的和；这样a[mid],lnum和lsum都可以通过划分树求出；问题就解决了，这题据说唯一一题不能用主席树求，学主席树去了。

【AC CODE】670ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int tol[20][MAXN],tree[20][MAXN],sot[MAXN];
LL sum[20][MAXN];

void bulid(int x, int y, int dep)
{
	if(x == y) return;
	int m = (x+y)>>1;
	int same = m-x+1;
	repe(i,x,y) if(tree[dep][i] < sot[m]) same--;
	int lpos = x, rpos = m+1;
	repe(i,x,y)
	{
		sum[dep][i] = sum[dep][i-1];
		if(tree[dep][i] < sot[m]) tree[dep+1][lpos++] = tree[dep][i], sum[dep][i] += tree[dep][i];
		else if(tree[dep][i] == sot[m] && same > 0) tree[dep+1][lpos++] = tree[dep][i], sum[dep][i] += tree[dep][i],same--;
		else tree[dep+1][rpos++] = tree[dep][i];
		tol[dep][i] = tol[dep][x-1]+lpos-x;
	}
	bulid(x,m,dep+1);
	bulid(m+1,y,dep+1);
}
LL lsum, lnum;//[ql,qr]中[ql,ql+k-1]（前k-1大）的所有数字之和以及个数
int query(int x, int y, int ql, int qr, int dep, int k)
{
	if(ql == qr) return tree[dep][ql];
	int m = (x+y)>>1, cnt = tol[dep][qr]-tol[dep][ql-1];
	if(cnt >= k)
	{
		int nx = x+tol[dep][ql-1]-tol[dep][x-1];
		int ny = nx+cnt-1;
		return query(x,m,nx,ny,dep+1,k);
	}
	int ny = qr+tol[dep][y]-tol[dep][qr];
	int nx = ny-(qr-ql-cnt);
	lnum += cnt;
	lsum += sum[dep][qr]-sum[dep][ql-1];
	return query(m+1,y,nx,ny,dep+1,k-cnt);
}
LL tmp[MAXN];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n;
		scanf("%d%*c", &n);
		repe(i,1,n) scanf("%d%*c", &tree[0][i]), sot[i] = tree[0][i], tmp[i] = tmp[i-1]+sot[i];
		clc(tol,0);
		sort(sot+1,sot+1+n);
		bulid(1,n,0);
		printf("Case #%d:\n",++count);
		int q;
		scanf("%d%*c", &q);
		while(q--)
		{
			int x,y;
			scanf("%d %d", &x, &y);
			x++,y++;
			int m = (y-x+2)>>1;
			lsum = lnum = 0;
			LL v = query(1,n,x,y,0,m);
			LL ans = v*(lnum-(y-x+1-lnum))+(tmp[y]-tmp[x-1]-lsum)-lsum;
			if(0 == (y-x+1)&1)
			{
				lsum = lnum = 0;
				v = query(1,n,x,y,0,m+1);
				LL buf = v*(lnum-(y-x+1-lnum))+(tmp[y]-tmp[x-1]-lsum)-lsum;
				ans = min(ans, buf);
			}
			printf("%I64d\n", ans);
		}
		putchar('\n');
	}
	return 0;
}