Minimum Sum

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

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

3 6 2 2 4

1 4

0 2

7 7

0 1

1 1

Sample Output

Case #1:

Case #2:

题意: 有n个元素的数组，有q次查询，对于每次询问，希望得到一个值x，使区间[L,R]内，的值最小。

思路:

既然要让这个值最小，那么这个区间内的中位数一定满足。不过这里还要处理这个区间里面小于中位数的值得和。

这时候，可以在建树的时候同时处理。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 1000000001#define MOD 1000000007#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define pi acos(-1.0)using namespace std;const int MAXN = 100010;int num[20][MAXN],cnt[20][MAXN],sor[MAXN],n,leftnum;ll sum[20][MAXN],leftsum,all[MAXN];//sum记录第d层 第i个数之前小于sor[m]的和void build(int l,int r,int d){ if(l == r){ return ; } int m = (l + r) >> 1; int same_m = m - l + 1; for(int i = l; i <= r; i++){ if(num[d][i] < sor[m])same_m --; } int cnt_small = 0; int pl,pr; ll val = 0; pl = l,pr = m + 1; for(int i = l; i <= r; i++){ if(num[d][i] < sor[m]){ cnt_small ++; val += num[d][i]; sum[d][i] = val; cnt[d][i] = cnt_small; num[d+1][pl++] = num[d][i]; } else if(num[d][i] == sor[m] && same_m){ same_m --; cnt_small ++; val += num[d][i]; sum[d][i] = val; cnt[d][i] = cnt_small; num[d+1][pl++] = num[d][i]; } else { sum[d][i] = val; cnt[d][i] = cnt_small; num[d+1][pr++] = num[d][i]; } } build(l,m,d+1); build(m+1,r,d+1);}ll query(int L,int R,int k,int l,int r,int d){ if(l == r){ return num[d][l]; } int m = (l + r) >> 1; int s,ss; ll val = 0; if(l == L)s = 0, val = sum[d][R]; else s = cnt[d][L-1], val = sum[d][R] - sum[d][L-1]; ss = cnt[d][R] - s; if(ss >= k){ int newl = l + s; int newr = l + s + ss - 1; return query(newl,newr,k,l,m,d+1); } else { leftnum += ss;//进入左孩子不用处理，进入右孩子时 就要加上左孩子的值 leftsum += val; int a = L - l - s; int b = R - L + 1 - ss; int newl = m + 1 + a; int newr = m + 1 + a + b - 1; return query(newl,newr,k - ss,m+1,r,d+1); }}int main(){ int t,ff = 0; scanf("%d",&t); while(t--){ scanf("%d",&n); memset(all,0,sizeof(all)); memset(num,0,sizeof(num)); for(int i = 1; i <= n; i++){ scanf("%d",&num[1][i]); sor[i] = num[1][i]; all[i] = all[i-1] + sor[i]; } sort(sor + 1,sor + n + 1); build(1,n,1); int q,x,y; scanf("%d",&q); printf("Case #%d:\n",++ff); while(q--){ scanf("%d%d",&x,&y); x += 1; y += 1; int len = (y - x + 1); ll tp; leftnum = 0; leftsum = 0; if(len % 2){ int k = (len + 1) >> 1; tp = query(x,y,k,1,n,1); } else { int k = len >> 1; tp = query(x,y,k,1,n,1); } //cout<
                 
                  <<' '<
                  
                   <<' '<
                   
                    <<' '<
                    
                     <<' '<
                     
                      <

转载于:https://www.cnblogs.com/sweat123/p/5543795.html

你可能感兴趣的文章