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

 

Recommend

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

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

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

！

！

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

。

。

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

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             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;}