HDU - 3473 Minimum Sum （划分树，额外处理获得区间小（大）于第k数的和）

You are given N positive integers, denoted as x0, x1 ... xN-1. Then give you some intervals [l, r]. For each interval, you need to find a number x to make as small as possible!

Input

The first line is an integer T (T <= 10), indicating the number of test cases. For each test case, an integer N (1 <= N <= 100,000) comes first. Then comes N positive integers x (1 <= x <= 1,000, 000,000) in the next line. Finally, comes an integer Q (1 <= Q <= 100,000), indicting there are Q queries. Each query consists of two integers l, r (0 <= l <= r < N), meaning the interval you should deal with. 
 

Output

For the k-th test case, first output “Case #k:” in a separate line. Then output Q lines, each line is the minimum value of  . Output a blank line after every test case.

Sample Input

2

5
3 6 2 2 4
2
1 4
0 2

2
7 7
2
0 1
1 1

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 200010;
int tree[20][maxn];
int sorted[maxn];
int toleft[20][maxn];
long long leftsum[20][maxn], lsum, rsum, sum[maxn];//所列出的东西只用在需要计算区间内比第k数大（小）的和时候才加
int lnum, rnum;//同上
void build(int l, int r, int dep) {
	if (l == r)return;
	int mid = (l + r) >> 1;
	int same = mid - l + 1;
	for (int i = l; i <= r; i++) {
		if (tree[dep][i] < sorted[mid])
			same--;
	}
	int lpos = l;
	int rpos = mid + 1;
	for (int i = l; i <= r; i++) {
		int spot = 0;
		if (tree[dep][i] < sorted[mid]) {
			tree[dep + 1][lpos++] = tree[dep][i];
			spot = 1;
		}
		else if (tree[dep][i] == sorted[mid] && same > 0) {
			tree[dep + 1][lpos++] = tree[dep][i];
			same--;	spot = 1;
		}
		else
			tree[dep + 1][rpos++] = tree[dep][i];
		leftsum[dep][i] = leftsum[dep][i - 1] + spot * tree[dep][i];//不需要时去除
		toleft[dep][i] = toleft[dep][l - 1] + lpos - l;
	}
	build(l, mid, dep + 1);
	build(mid + 1, r, dep + 1);
}
int query(int L, int R, int l, int r, int dep, int k) {
	if (l == r)return tree[dep][l];
	int mid = (L + R) >> 1;
	int cnt = toleft[dep][r] - toleft[dep][l - 1];
	if (cnt >= k) {
		int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
		int newr = newl + cnt - 1;
		return query(L, mid, newl, newr, dep + 1, k);
	}
	else {
		int newr = r + toleft[dep][R] - toleft[dep][r];
		int newl = newr - (r - l - cnt);
		lnum += cnt;//不需要时去除
		lsum += leftsum[dep][r] - leftsum[dep][l - 1];//不需要时去除
		return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
	}
}
int main() {
	int n, m;
	int te; scanf("%d", &te);
	sum[0] = 0;
	for (int i = 0; i < 20; i++)
		leftsum[i][0] = 0;
	int cas = 1;
	while (te--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &tree[0][i]);
			sorted[i] = tree[0][i];
			sum[i] = sum[i - 1] + tree[0][i];
		}
		sort(sorted + 1, sorted + n + 1);
		build(1, n, 0);
		int s, t, k;
		scanf("%d", &m);
		printf("Case #%d:\n", cas++);
		while (m--) {
			scanf("%d%d", &s, &t);
			s++, t++;//!
			lsum = lnum = 0;
			k = (t - s) / 2 + 1;//中位数的所在序号
			int spot = query(1, n, s, t, 0, k);	//中位数是多少
			rnum = (t - s + 1 - lnum);//排序后比所求spot（包含spot这个点）右边的数的数量，lsum相反（不包括spot）
			rsum = (sum[t] - sum[s - 1] - lsum);//排序后比所求spot（包含spot这个点）右边的数的和，rsum相反（不包括spot）
			long long ans = rsum - lsum + spot * (lnum - rnum);
			printf("%lld\n", ans);
		}
		printf("\n");
	}
	return 0;
}