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
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

Source

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

Recommend

zhengfeng   |   We have carefully selected several similar problems for you:  

pid=3474">3474

 1828 3397 

pid=3333">3333

 3472





被杭电的输出坑了 好久。。。。

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

！

！

易得使绝对值和最小就是中位数，能够參考坐标上的点到两点间距离之和最小的原理。

。

。

这道题让我对划分树的原理理解更加深刻了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
#define md(x, y) (((x)+(y))>>1)
const int maxn = 100000+10;
typedef long long LL;
int n,m;
int ls;
int num[maxn];
int seg[20][maxn];
int lftnum[20][maxn];
LL lfts[20][maxn];
LL presum[maxn];
LL lsum;
void build(int L,int R,int dep){
    if(L==R)return;
    int mid = md(L,R);
    int key = num[mid];
    int lcnt = mid-L+1;
    for(int i = L; i <= R; i++){
        if(seg[dep][i] < key)
            lcnt--;
    }
    int lp = L,rp = mid+1;
    for(int i = L; i <= R; i++){
        if(i==L){
            lftnum[dep][i] = 0;
            lfts[dep][i] = 0;
        }else{
            lfts[dep][i] = lfts[dep][i-1];
            lftnum[dep][i] = lftnum[dep][i-1];
        }
        if(seg[dep][i] < key){
            lftnum[dep][i]++;
            lfts[dep][i] += seg[dep][i];
            seg[dep+1][lp++] = seg[dep][i];
        }
        else if(seg[dep][i] > key){
            seg[dep+1][rp++] = seg[dep][i];
        }
        else{
            if(lcnt>0){
                lcnt--;
                lftnum[dep][i]++;
                lfts[dep][i] += seg[dep][i];
                seg[dep+1][lp++] = seg[dep][i];
            }else{
                seg[dep+1][rp++] = seg[dep][i];
            }
        }
    }

    build(L,mid,dep+1);
    build(mid+1,R,dep+1);
}

LL query(int L,int R,int ll,int rr,int dep,int k){
    if(ll == rr)
        return seg[dep][ll];
    int mid = md(ll,rr);
    int ncnt,ucnt;
    LL tsum = 0;
    if(L==ll){
        ncnt = 0;
        tsum = lfts[dep][R];
        ucnt = lftnum[dep][R]-ncnt;
    }else{
        ncnt = lftnum[dep][L-1];
        ucnt = lftnum[dep][R]-ncnt;
        tsum = lfts[dep][R]-lfts[dep][L-1];
    }
    if(ucnt >= k){
        L = ll + ncnt;
        R = ll + ncnt + ucnt-1;
        return query(L,R,ll,mid,dep+1,k);
    }else{
        int aa = L-ll-ncnt;
        int bb = R-L-ucnt+1;
        L = mid+aa+1;
        R = mid+aa+bb;
        ls += ucnt;
        lsum += tsum;
        return query(L,R,mid+1,rr,dep+1,k-ucnt);
    }
}
int main(){

    int ncase,T=1;
    cin >>ncase;
    while(ncase--){
        scanf("%d",&n);
        presum[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d",&num[i]);
            seg[0][i] = num[i];
            presum[i] = presum[i-1]+num[i];
        }
        sort(num+1,num+n+1);
        build(1,n,0);
        scanf("%d",&m);
        printf("Case #%d:\n",T++);
        while(m--){
            int a,b,k;
            scanf("%d%d",&a,&b);
            ++a;++b;
            k = (b-a)/2+1;
            lsum = 0;
            ls = 0;
            int rs = 0;
            int t = query(a,b,1,n,0,k);
            LL rsum = presum[b]-presum[a-1]-t-lsum;
            rs = b-a-ls;
            LL ans = rsum-lsum+t*(ls-rs);
            printf("%I64d\n",ans);
        }
        printf("\n");
    }
    return 0;
}