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:
",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
",ans);
114         }
115         printf("
");
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         else
103         {
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_JUDGE
127         freopen("in.txt","r",stdin);
128         freopen("wa.txt","w",stdout);
129     #endif
130     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:
",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
",rsum - x2 - (lsum - x1) +  (lnum - rnum) * mid_num);
171         }
172         printf("
");
173     }
174     return 0;
175 
176 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/oneshot/p/4127018.html