首页 > 代码库 > HDU3473--Minimum Sum(静态区间第k大)

HDU3473--Minimum Sum(静态区间第k大)

Minimum Sum

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


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
 

区间第k大的题目一般两种做法,,划分树 主席树,不过貌似划分树只支持静态区间第k大。


这道题由于内存限制 只能用划分树。。具体就是 先找出区间[l,r]内的中位数,(为什么是中位数,大白书貌似有介绍),然后直接求和。

MLE到死啊,,注释memset部分之后就过了,不知道为什么
划分树代码:

 

  1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cstdio>  8 #include <string>  9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 100010; 20 int sorted[maxn],tree[20][maxn],toleft[20][maxn];   //toleft[dep][i]表示第dep层1-i中进入左子树元素的个数 21 ll leftsum[20][maxn], sum[maxn];              //leftsum[dep][i]表示第dep层1-i中进入左子树元素的和 22  23 void build (int l,int r,int dep) 24 { 25     if (l == r) 26         return; 27     int mid = (l + r) >> 1; 28     int same = mid - l + 1; 29     for (int i = l; i <= r; i++) 30         if (tree[dep][i] < sorted[mid]) 31             same--; 32     int lpos = l,rpos = mid + 1; 33     for (int i = l; i <= r; i++) 34     { 35         if (tree[dep][i] < sorted[mid]) 36         { 37             tree[dep+1][lpos++] = tree[dep][i]; 38             leftsum[dep][i] = leftsum[dep][i-1] + tree[dep][i]; 39         } 40         else if (tree[dep][i] == sorted[mid] && same > 0) 41         { 42             tree[dep+1][lpos++] = tree[dep][i]; 43             leftsum[dep][i] = leftsum[dep][i-1] + tree[dep][i]; 44             same--; 45         } 46         else 47         { 48             tree[dep+1][rpos++] = tree[dep][i]; 49             leftsum[dep][i] = leftsum[dep][i-1]; 50         } 51         toleft[dep][i] = toleft[dep][l-1] + lpos - l; 52     } 53     build (l,mid,dep+1); 54     build (mid+1,r,dep+1); 55 } 56 int lnum,rnum; 57 ll lsum,rsum; 58 int query(int l,int r,int dep,int ua,int ub,int k) 59 { 60     if (ua == ub) 61         return tree[dep][ua]; 62     int mid = (l + r) >> 1; 63     int cnt = toleft[dep][ub] - toleft[dep][ua-1]; 64     if (cnt >= k) 65     { 66         int newl = l + toleft[dep][ua-1] - toleft[dep][l-1]; 67         int newr = newl + cnt - 1; 68         return query(l,mid,dep+1,newl,newr,k); 69     } 70     else 71     { 72         int newr = ub + toleft[dep][r] - toleft[dep][ub]; 73         int newl = newr - (ub - ua - cnt); 74         lnum += cnt; 75         lsum += leftsum[dep][ub] - leftsum[dep][ua-1]; 76         return query(mid+1,r,dep+1,newl,newr,k-cnt); 77     } 78 } 79  80 int main(void) 81 { 82     #ifndef ONLINE_JUDGE 83         freopen("in.txt","r",stdin); 84     #endif 85     int T, cas = 1; 86     scanf ("%d",&T); 87     while (T--) 88     { 89         int n,m; 90         scanf ("%d",&n); 91         sum[0] = 0; 92         for (int i = 1; i <= n; i++) 93         { 94             scanf ("%d",&tree[0][i]); 95             sum[i] = sum[i-1] + tree[0][i]; 96             sorted[i] = tree[0][i]; 97         } 98         sort(sorted+1,sorted+n+1); 99         build (1,n,0);100         scanf ("%d",&m);101         printf ("Case #%d:\n",cas++);102         while (m--)103         {104             int u, v;105             scanf ("%d%d",&u,&v);106             u++,v++;107             lnum = 0;108             lsum = 0;109             int mid_num = query(1,n,0,u,v,(v-u)/2+1);             //中位数110             rnum = (v - u + 1 - lnum);                            // u~v 区间内大于mid_num的个数111             rsum = (sum[v] - sum[u-1] - lsum);                    //u~v    区间内大于mid_num的数的和112             ll ans = rsum - lsum + mid_num * (lnum - rnum);113             printf("%I64d\n",ans);114         }115         printf("\n");116     }117     return 0;118 }

主席树部分代码:(主席树会MLE,已经和划分树代码对拍过,应该没问题)

  1 typedef long long ll;   2 const int maxn = 1e5+10;  3 int n,q,tot;  4   5 //主席树部分  6 int lson[maxn*20],rson[maxn*20],c[maxn*20],tree[maxn];  7   8 ll sum[maxn*20];  9 int build (int l,int r) 10 { 11     int root = tot++; 12     c[root] = 0; 13     sum[root] = 0; 14     if (l != r) 15     { 16         int mid = (l + r) >> 1; 17         lson[root] = build(l,mid); 18         rson[root] = build(mid+1,r); 19     } 20     return root; 21 } 22 int update(int root,int pos,int val,int k) 23 { 24     int newroot = tot++; 25     int tmp = newroot; 26     int l = 1, r = n; 27     c[newroot] = c[root] + val; 28     sum[newroot] = sum[root] + k; 29     while (l < r) 30     { 31         int mid = (l + r) >> 1; 32         if (pos <= mid) 33         { 34             rson[newroot] = rson[root]; 35             root = lson[root]; 36             lson[newroot] = tot++; 37             newroot = lson[newroot]; 38             r = mid; 39         } 40         else 41         { 42             lson[newroot] = lson[root]; 43             root = rson[root]; 44             rson[newroot] = tot++; 45             newroot = rson[newroot]; 46             l = mid + 1; 47         } 48         c[newroot] = c[root] + val; 49         sum[newroot] = sum[root] + k; 50     } 51     return tmp; 52 } 53 ll lsum,rsum;                       //lsum小于中位数的和,rsum大于中位数的和 54 ll query(int root,int l,int r,int ua,int ub)                  //查询1-root 大于ua小于ub的和 55 { 56     if (ub < ua) 57         return 0; 58     if (ua <= l && ub >= r) 59     { 60         return sum[root]; 61     } 62     int mid = (l + r) >> 1; 63     ll t1 = 0,t2 = 0; 64     if (ua <= mid) 65         t1 = query(lson[root],l,mid,ua,ub); 66     if (ub > mid) 67         t2 = query(rson[root],mid+1,r,ua,ub); 68     return t1 + t2; 69 } 70 int query1(int root,int l,int r,int ua,int ub)               //查询1-root  在ua ub 之间的数的个数 71 { 72     if (ub < ua) 73         return 0; 74     if (ua <= l && ub >= r) 75     { 76         return c[root]; 77     } 78     int mid = (l + r) >> 1; 79     int t1 = 0,t2 = 0; 80     if (ua <= mid) 81         t1 = query1(lson[root],l,mid,ua,ub); 82     if (ub > mid) 83         t2 = query1(rson[root],mid+1,r,ua,ub); 84     return t1 + t2; 85 } 86 int query(int left,int right,int k)                                 //查询left right区间第k大  87 { 88     int l_root = tree[left-1]; 89     int r_root = tree[right]; 90     int l = 1, r = n; 91     while (l < r) 92     { 93         int mid = (l + r) >> 1; 94         int tmp = c[lson[r_root]] - c[lson[l_root]]; 95         if (tmp <= k) 96         { 97             k -= tmp; 98             r_root = rson[r_root]; 99             l_root = rson[l_root];100             l = mid + 1;101         }102         else103         {104             l_root = lson[l_root];105             r_root = lson[r_root];106             r = mid;107         }108     }109     return l;110 }111 int vec[maxn],rel[maxn],idx;112 //离散化113 inline void init_hash()114 {115     sort(vec,vec+idx);116     idx = unique(vec,vec+idx) - vec;117 }118 inline int _hash(ll x)119 {120     return lower_bound(vec,vec+idx,x) - vec + 1;121 }122 123 124 int main(void)125 {126     #ifndef ONLINE_JUDGE127         freopen("in.txt","r",stdin);128         freopen("wa.txt","w",stdout);129     #endif130     int t,cas = 1;131     scanf ("%d",&t);132     while (t--)133     {134         memset(sum,0,sizeof(sum));135         scanf ("%d",&n);136         idx = tot = 0;137         for (int i = 1; i<= n; i++)138         {139             //scanf ("%d",a+i);140             scanf ("%d",tree+i);141             vec[idx++] = tree[i];142         }143         init_hash();144         tree[0] = build(1,n);145         for (int i = 1; i <= n; i++)146         {147             int tmp = _hash(tree[i]);148             rel[tmp] = tree[i];149 150             tree[i] = update(tree[i-1],tmp,1,tree[i]);151             //tree[i] = tmp2;152         }153         scanf ("%d",&q);154         printf("Case #%d:\n",cas++);155         while (q--)156         {157             int u,v;158             scanf ("%d%d",&u,&v);159             u++,v++;160             int vir_mid = query(u,v,(v-u)/2);161             int mid_num = rel[vir_mid];                //中位数162             lsum = query(tree[u-1],1,n,1,vir_mid-1);163             rsum = query(tree[u-1],1,n,vir_mid+1,n);164             ll x1 = lsum, x2 = rsum;165 166             lsum = query(tree[v],1,n,1,vir_mid-1);167             rsum = query(tree[v],1,n,vir_mid+1,n);168             int lnum = query1(tree[v],1,n,1,vir_mid - 1) - query1(tree[u-1],1,n,1,vir_mid - 1);169             int rnum = query1(tree[v],1,n,vir_mid + 1,n) - query1(tree[u-1],1,n,vir_mid + 1,n);170             printf("%I64d\n",rsum - x2 - (lsum - x1) +  (lnum - rnum) * mid_num);171         }172         printf("\n");173     }174     return 0;175 176 }

 

HDU3473--Minimum Sum(静态区间第k大)