HDU-3473Minimum Sum

Problem Description

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

1 4

0 2

7 7

0 1

1 1

Sample Output

Case #1:

6

4

Case #2:

Author

standy

Source

2010

ACM-ICPC Multi-University Training Contest（4）——Host by UESTC

Recommend

zhengfeng   |   We have carefully selected several similar problems for you:  3474 1828 3397 3333 3472

被杭電的輸出坑了 好久。。。。

printf lld 就WA 要I64d才行。。。。。真吭。！

！

易得使絕對值和最小就是中位數，能夠參考坐标上的點到兩點間距離之和最小的原理。

。

這道題讓我對劃分樹的原理了解更加深刻了。