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!
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.
. 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:
区间第k大的题目一般两种做法，，划分树 主席树，不过貌似划分树只支持静态区间第k大。
这道题由于内存限制 只能用划分树。。具体就是 先找出区间[l,r]内的中位数，（为什么是中位数，大白书貌似有介绍），然后直接求和。
MLE到死啊，，注释memset部分之后就过了，不知道为什么
划分树代码：
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = ;
int sorted[maxn],tree[][maxn],toleft[][maxn]; //toleft[dep][i]表示第dep层1-i中进入左子树元素的个数
ll leftsum[][maxn], sum[maxn]; //leftsum[dep][i]表示第dep层1-i中进入左子树元素的和 void build (int l,int r,int dep)
{
if (l == r)
return;
int mid = (l + r) >> ;
int same = mid - l + ;
for (int i = l; i <= r; i++)
if (tree[dep][i] < sorted[mid])
same--;
int lpos = l,rpos = mid + ;
for (int i = l; i <= r; i++)
{
if (tree[dep][i] < sorted[mid])
{
tree[dep+][lpos++] = tree[dep][i];
leftsum[dep][i] = leftsum[dep][i-] + tree[dep][i];
}
else if (tree[dep][i] == sorted[mid] && same > )
{
tree[dep+][lpos++] = tree[dep][i];
leftsum[dep][i] = leftsum[dep][i-] + tree[dep][i];
same--;
}
else
{
tree[dep+][rpos++] = tree[dep][i];
leftsum[dep][i] = leftsum[dep][i-];
}
toleft[dep][i] = toleft[dep][l-] + lpos - l;
}
build (l,mid,dep+);
build (mid+,r,dep+);
}
int lnum,rnum;
ll lsum,rsum;
int query(int l,int r,int dep,int ua,int ub,int k)
{
if (ua == ub)
return tree[dep][ua];
int mid = (l + r) >> ;
int cnt = toleft[dep][ub] - toleft[dep][ua-];
if (cnt >= k)
{
int newl = l + toleft[dep][ua-] - toleft[dep][l-];
int newr = newl + cnt - ;
return query(l,mid,dep+,newl,newr,k);
}
else
{
int newr = ub + toleft[dep][r] - toleft[dep][ub];
int newl = newr - (ub - ua - cnt);
lnum += cnt;
lsum += leftsum[dep][ub] - leftsum[dep][ua-];
return query(mid+,r,dep+,newl,newr,k-cnt);
}
} int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T, cas = ;
scanf ("%d",&T);
while (T--)
{
int n,m;
scanf ("%d",&n);
sum[] = ;
for (int i = ; i <= n; i++)
{
scanf ("%d",&tree[][i]);
sum[i] = sum[i-] + tree[][i];
sorted[i] = tree[][i];
}
sort(sorted+,sorted+n+);
build (,n,);
scanf ("%d",&m);
printf ("Case #%d:\n",cas++);
while (m--)
{
int u, v;
scanf ("%d%d",&u,&v);
u++,v++;
lnum = ;
lsum = ;
int mid_num = query(,n,,u,v,(v-u)/+); //中位数
rnum = (v - u + - lnum); // u~v 区间内大于mid_num的个数
rsum = (sum[v] - sum[u-] - lsum); //u~v 区间内大于mid_num的数的和
ll ans = rsum - lsum + mid_num * (lnum - rnum);
printf("%I64d\n",ans);
}
printf("\n");
}
return ;
}
主席树部分代码：（主席树会MLE，已经和划分树代码对拍过，应该没问题）
typedef long long ll;
const int maxn = 1e5+;
int n,q,tot; //主席树部分
int lson[maxn*],rson[maxn*],c[maxn*],tree[maxn]; ll sum[maxn*];
int build (int l,int r)
{
int root = tot++;
c[root] = ;
sum[root] = ;
if (l != r)
{
int mid = (l + r) >> ;
lson[root] = build(l,mid);
rson[root] = build(mid+,r);
}
return root;
}
int update(int root,int pos,int val,int k)
{
int newroot = tot++;
int tmp = newroot;
int l = , r = n;
c[newroot] = c[root] + val;
sum[newroot] = sum[root] + k;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
rson[newroot] = rson[root];
root = lson[root];
lson[newroot] = tot++;
newroot = lson[newroot];
r = mid;
}
else
{
lson[newroot] = lson[root];
root = rson[root];
rson[newroot] = tot++;
newroot = rson[newroot];
l = mid + ;
}
c[newroot] = c[root] + val;
sum[newroot] = sum[root] + k;
}
return tmp;
}
ll lsum,rsum; //lsum小于中位数的和，rsum大于中位数的和
ll query(int root,int l,int r,int ua,int ub) //查询1-root 大于ua小于ub的和
{
if (ub < ua)
return ;
if (ua <= l && ub >= r)
{
return sum[root];
}
int mid = (l + r) >> ;
ll t1 = ,t2 = ;
if (ua <= mid)
t1 = query(lson[root],l,mid,ua,ub);
if (ub > mid)
t2 = query(rson[root],mid+,r,ua,ub);
return t1 + t2;
}
int query1(int root,int l,int r,int ua,int ub) //查询1-root 在ua ub 之间的数的个数
{
if (ub < ua)
return ;
if (ua <= l && ub >= r)
{
return c[root];
}
int mid = (l + r) >> ;
int t1 = ,t2 = ;
if (ua <= mid)
t1 = query1(lson[root],l,mid,ua,ub);
if (ub > mid)
t2 = query1(rson[root],mid+,r,ua,ub);
return t1 + t2;
}
int query(int left,int right,int k) //查询left right区间第k大
{
int l_root = tree[left-];
int r_root = tree[right];
int l = , r = n;
while (l < r)
{
int mid = (l + r) >> ;
int tmp = c[lson[r_root]] - c[lson[l_root]];
if (tmp <= k)
{
k -= tmp;
r_root = rson[r_root];
l_root = rson[l_root];
l = mid + ;
}
else
{
l_root = lson[l_root];
r_root = lson[r_root];
r = mid;
}
}
return l;
}
int vec[maxn],rel[maxn],idx;
//离散化
inline void init_hash()
{
sort(vec,vec+idx);
idx = unique(vec,vec+idx) - vec;
}
inline int _hash(ll x)
{
return lower_bound(vec,vec+idx,x) - vec + ;
} int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("wa.txt","w",stdout);
#endif
int t,cas = ;
scanf ("%d",&t);
while (t--)
{
memset(sum,,sizeof(sum));
scanf ("%d",&n);
idx = tot = ;
for (int i = ; i<= n; i++)
{
//scanf ("%d",a+i);
scanf ("%d",tree+i);
vec[idx++] = tree[i];
}
init_hash();
tree[] = build(,n);
for (int i = ; i <= n; i++)
{
int tmp = _hash(tree[i]);
rel[tmp] = tree[i]; tree[i] = update(tree[i-],tmp,,tree[i]);
//tree[i] = tmp2;
}
scanf ("%d",&q);
printf("Case #%d:\n",cas++);
while (q--)
{
int u,v;
scanf ("%d%d",&u,&v);
u++,v++;
int vir_mid = query(u,v,(v-u)/);
int mid_num = rel[vir_mid]; //中位数
lsum = query(tree[u-],,n,,vir_mid-);
rsum = query(tree[u-],,n,vir_mid+,n);
ll x1 = lsum, x2 = rsum; lsum = query(tree[v],,n,,vir_mid-);
rsum = query(tree[v],,n,vir_mid+,n);
int lnum = query1(tree[v],,n,,vir_mid - ) - query1(tree[u-],,n,,vir_mid - );
int rnum = query1(tree[v],,n,vir_mid + ,n) - query1(tree[u-],,n,vir_mid + ,n);
printf("%I64d\n",rsum - x2 - (lsum - x1) + (lnum - rnum) * mid_num);
}
printf("\n");
}
return ; }