转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
对于xl,xl+1……xr,使得[xi-x]和最小,显然x应当为其中的中位数。中位数可以通过求K大数解决,划分树可搞。
对于求和,分为两部分,小于x的部分,大于y的部分,在建树的时候也保存下来分到左子树中的数的和。
最终的和为ave*(lnum-rnum)+rsum-lsum
ave为中位数,lnum为左子数的数量,也就是小于中位数的数量,rnum为右子数,lsum表示小于中位数部分的和
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
#define LL __int64
using namespace std;
struct Node{
int left,right,mid;
}tree[N*4];
int sa[N],num[20][N],cnt[20][N]; //sa中是排序后的,num记录每一层的排序结果,cnt[deep][i]表示第deep层,前i个数中有多少个进入左子树
LL Lsum[20][N],sum[N];
int n,q;
void debug(int d){
for(int i=1;i<=n;i++)
printf("%d ",num[d][i]);
printf("\n");
}
void bulid(int step,int l,int r,int deep){
tree[step].left=l;
tree[step].right=r;
tree[step].mid=(l+r)>>1;
if(l==r)
return;
int mid=(l+r)>>1;
int mid_val=sa[mid],lsum=mid-l+1;;
for(int i=l;i<=r;i++)
if(num[deep][i]<mid_val)
lsum--; //lsum表示左子树中还需要多少个中值
int L=l,R=mid+1;
Lsum[deep][0]=0;
for(int i=l;i<=r;i++){
if(i==l)
cnt[deep][i]=0;
else
cnt[deep][i]=cnt[deep][i-1];
Lsum[deep][i]=Lsum[deep][i-1];
if(num[deep][i]<mid_val||(num[deep][i]==mid_val&&lsum>0)){ //左子树
num[deep+1][L++]=num[deep][i];
cnt[deep][i]++;
Lsum[deep][i]+=(LL)num[deep][i];
if(num[deep][i]==mid_val)
lsum--;
}
else
num[deep+1][R++]=num[deep][i];
}
// debug(deep);
bulid(2*step,l,mid,deep+1);
bulid(2*step+1,mid+1,r,deep+1);
}
int lnum;
LL lsum;
int query(int step,int l,int r,int k,int deep){
if(l==r)
return num[deep][l];
int s1,s2; //s1为[tree[step].left,l-1]中分到左子树的个数
if(tree[step].left==l)
s1=0;
else
s1=cnt[deep][l-1];
s2=cnt[deep][r]-s1; //s2为[l,r]中分到左子树的个数
if(k<=s2) //左子树的数量大于k,递归左子树
return query(2*step,tree[step].left+s1,tree[step].left+s1+s2-1,k,deep+1);
int b1=l-1-tree[step].left+1-s1; //b1为[tree[step].left,l-1]中分到右子树的个数
int b2=r-l+1-s2; //b2为[l,r]中分到右子树的个数
lnum+=s2;
lsum=(LL)lsum+Lsum[deep][r]-Lsum[deep][l-1];
return query(2*step+1,tree[step].mid+1+b1,tree[step].mid+1+b1+b2-1,k-s2,deep+1);
}
int main(){
int cas=0;
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n) ;
sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&num[1][i]);
sa[i]=num[1][i];
sum[i]=(LL)sum[i-1]+sa[i];
}
sort(sa+1,sa+n+1);
bulid(1,1,n,1);
scanf("%d",&q);
printf("Case #%d:\n",++cas);
while(q--){
int l,r,k;
scanf("%d%d",&l,&r);
l++;r++;
k=(r-l+2)>>1;
lnum=0;
lsum=0;
int ave=query(1,l,r,k,1);
printf("%I64d\n",(LL)ave*(lnum-(r-l+1-lnum))+sum[r]-sum[l-1]-lsum-lsum);
}
puts("");
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
hdu 1166线段树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
自己做的HDU ACM已经AC的题目