hdu 3473 （划分树）2

Minimum Sum

Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4611 Accepted Submission(s): 1046

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 2 1 4 0 2 2 7 7 2 0 1 1 1

Sample Output

Case #1: 6 4 Case #2: 0 0

Author

standy

裸题我都不会我废了

现在还是懵逼状态

ans= 【L，R 】（中位数左边的值-中位数右边的值）如果注意一下这个区间元素的个数

用一个sum数组累加

当进入左子树查找时ans+=查询区间进入右子树的元素和

当进入右子树查询时ans-=查询区间进入左子树的元素和。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 1e5 + 10;
 8 int sorted[maxn];
 9 int num[20][maxn], val[20][maxn];
10 LL sum[20][maxn];
11 
12 void build(int l, int r, int dep) {
13     if (l == r) {
14         sum[dep][l] = sum[dep][l - 1] + val[dep][l];
15         return ;
16     }
17     int mid = (l + r) >> 1, same = mid - l + 1;
18     for (int i = l ; i <= r ; i++) {
19         if (val[dep][i] < sorted[mid]) same--;
20         sum[dep][i] += sum[dep][i - 1] + val[dep][i];
21     }
22     int lpos = l, rpos = mid + 1;
23     for (int i = l ; i <= r ; i++) {
24         if (val[dep][i] < sorted[mid]) val[dep + 1][lpos++] = val[dep][i];
25         else if (val[dep][i] == sorted[mid] && same > 0) {
26             val[dep + 1][lpos++] = val[dep][i];
27             same--;
28         } else val[dep + 1][rpos++] = val[dep][i];
29         num[dep][i] = num[dep][l - 1] + lpos - l;
30     }
31     build(l, mid, dep + 1) ;
32     build(mid + 1, r, dep + 1);
33 }
34 LL ans;
35 
36 int query(int L, int R, int l, int r, int dep, int k) {
37     if (l == r) return val[dep][l];
38     int mid = (L + R) >> 1;
39     int cnt = num[dep][r] - num[dep][l - 1];
40     if (cnt >= k) {
41         int ee = r - L + 1 - (num[dep][r] - num[dep][L - 1]) + mid;
42         int ss = l - L - (num[dep][l - 1] - num[dep][L - 1]) + mid;
43         ans += sum[dep + 1][ee] - sum[dep + 1][ss];
44         int newl = L + num[dep][l - 1] - num[dep][L - 1];
45         int newr = newl + cnt - 1;
46         return query(L, mid, newl, newr, dep + 1, k);
47     } else {
48         int s = L + num[dep][l - 1] - num[dep][L - 1];
49         int e = s + cnt - 1;
50         ans -= sum[dep + 1][e] - sum[dep + 1][s - 1];
51         int newr = r + num[dep][R] - num[dep][r];
52         int newl = newr - (r - l + 1 - cnt) + 1;
53         return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
54     }
55 }
56 
57 int main() {
58     int t, n, cas = 1, m, l, r;
59     scanf("%d", &t);
60     while(t--) {
61         scanf("%d", &n);
62         memset(val, 0, sizeof(val));
63         memset(sum, 0, sizeof(sum));
64         for (int i = 1 ; i <= n ; i++)  {
65             scanf("%d", &val[0][i]);
66             sorted[i] = val[0][i];
67         }
68         sort(sorted + 1, sorted + n + 1);
69         build(1, n, 0);
70         printf("Case #%d:
", cas++);
71         scanf("%d", &m);
72         while(m--) {
73             scanf("%d%d", &l, &r);
74             ans = 0;
75             l++, r++;
76             int temp = query(1, n, l, r, 0, (l + r) / 2 - l + 1);
77             if ((l + r) % 2) ans -= temp;
78             printf("%lld
", ans);
79         }
80         printf("
");
81     }
82     return 0;
83 }