HDU 3473-Minimum Sum(划分树-求区间sigma最小值)

╰+哭是因爲堅強的太久メ 2022-08-22 00:11 130阅读 0赞

# Minimum Sum #

**Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 3710 Accepted Submission(s): 852**

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 ![C284-1005-1.jpg][] 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 ![C284-1005-1.jpg][] . 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 ][2010 ACM-ICPC Multi-University Training Contest_4_Host by UESTC]

Recommend

zhengfeng | We have carefully selected several similar problems for you: [3474][] [1828][] [1698][] [1540][] [1394][]

## 题目意思： ##

有一组数，求区间l~r内的一个数，使得sigma值最小。

## 解题思路： ##

划分树找到中位数ave，建树的时候用lsum数组保存分到左子树中的数的和。  
  
对于lsum数组的生成说明如下：  
举个栗子： ![Center][]  
  
![Center 1][]  
  
![Center 2][]  
  
![Center 3][]  
  
求解ans时可以分成求中位数左边和+中位数右边和。  
具体可以看注释。

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define N 100050
    using namespace std;
    
    int sorted[N];   //排序完的数组
    int toleft[30][N]; //toleft[i][j]表示第i层从1到k有多少个数分入左边
    int tree[30][N];  //表示每层每个位置的值
    int n;//输入的数的个数
    long long sum[N];//保存包括当前位置及之前的所有元素之和
    long long lsum[30][N];//在deep层 第i个元素在的区间中 在i前面被划分到左子树的元素之和
    long long tsum;//表示小于中位数ave部分的和
    
    void building(int l,int r,int dep)
    {
        if(l==r) return;
        int mid = (l+r)>>1;
        int temp = sorted[mid];
        int i,sum_same=mid-l+1;//表示等于中间值而且被分入左边的个数
        for(i=l; i<=r; i++)
            if(tree[dep][i]<temp)
                sum_same--;
        int leftpos = l;
        int rightpos = mid+1;
        for(i=l; i<=r; i++)
        {
            if(tree[dep][i]<temp)//比中间的数小，分入左边
            {
                tree[dep+1][leftpos++]=tree[dep][i];
                lsum[dep][i] = lsum[dep][i-1] + tree[dep][i];//记录被划分到左边的和是多少
            }
            else if(tree[dep][i]==temp&&sum_same>0)//等于中间的数值，分入左边，直到sum==0后分到右边
            {
                tree[dep+1][leftpos++]=tree[dep][i];
                lsum[dep][i] = lsum[dep][i-1] + tree[dep][i];
                sum_same--;
            }
            else //右边
            {
                tree[dep+1][rightpos++]=tree[dep][i];
                lsum[dep][i] = lsum[dep][i-1];
            }
            toleft[dep][i] = toleft[dep][l-1] + leftpos - l;   //从1到i放左边的个数
        }
        building(l,mid,dep+1);
        building(mid+1,r,dep+1);
    }
    
    //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间
    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]; //[l,r]中位于左边的个数
        if(cnt>=k)
        {
            int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; //L+要查询的区间前被放在左边的个数
            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);
            tsum+=lsum[dep][r]-lsum[dep][l-1];//区间
        }
    }
    
    int main()
    {
        int t,cas=1;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            int i;
            for(i=1; i<=n; i++)
            {
                scanf("%lld",&sorted[i]);
                sum[i] = sum[i-1]+sorted[i];//保存包括当前位置及之前的所有元素之和
                tree[0][i]=sorted[i] ;
            }
            sort(sorted+1,sorted+1+n);
            building(1,n,0);
            int l,r;
            int m;//查询次数
            scanf("%d",&m);
            printf("Case #%d:\n",cas++);
            while(m--)
            {
                scanf("%d%d",&l,&r);
                l++,r++;
                tsum=0;//表示小于中位数ave部分的和
                int k=(r-l)/2+1;//k是区间ab的中位数
                long long ave= query(1,n,l,r,0,k);//ave是中位数的值，r-l+1-k是左边数的个数
                long long ans=sum[r]-sum[l-1]-ave*(r-l+1-k)-tsum-ave;//中位数右边和，大于ave的部分
                ans+=(k-1)*ave-tsum;//中位数左边和，小于ave的部分
                printf("%lld\n",ans);
            }
            printf("\n");
        }
        return 0;
    }

[C284-1005-1.jpg]: /images/20220724/841d921fe3ec4fd8b0fae2886a126f53.png
[2010 ACM-ICPC Multi-University Training Contest_4_Host by UESTC]: http://acm.hdu.edu.cn/search.php?field=problem&key=2010+ACM-ICPC+Multi-University+Training+Contest%A3%A84%A3%A9%A1%AA%A1%AAHost+by+UESTC&source=1&searchmode=source
[3474]: http://acm.hdu.edu.cn/showproblem.php?pid=3474
[1828]: http://acm.hdu.edu.cn/showproblem.php?pid=1828
[1698]: http://acm.hdu.edu.cn/showproblem.php?pid=1698
[1540]: http://acm.hdu.edu.cn/showproblem.php?pid=1540
[1394]: http://acm.hdu.edu.cn/showproblem.php?pid=1394
[Center]: /images/20220724/f1d839a90d374d43919b74987b803a36.png
[Center 1]: /images/20220724/7cc08437286b4bba9aeeb92104b1b5f9.png
[Center 2]: /images/20220724/30502a019ce44b27a232ba174ba85a08.png
[Center 3]: /images/20220724/31ef0975227143278c4733241b85c06d.png