????????????????????????????????????????????????? Minimum Sum

? 被這個題坑了一下午，原來只需找一個最中間的數即可，我以為是平均數。

? 題意：找一個數使得這個數和區間內所有數的差的絕對值最小。輸出最小值。

? 開始用線段樹來了一發果斷T了，然后各種優化依然T不斷。于是只能用劃分樹做。不過，其實熟悉劃分樹也是模板水題。

? 打一個前綴和，然后這個數肯定是這個區間從大到小排在最中間的。所以查詢一遍將小于中間這個數的和加起來，然后得到將小于這個數的個數。分為前半段和后半段分別加起來即可。

? 手殘將一個地方寫錯了，然后無限RE。。。。最后一行一行debug，心塞。

ll sum[N],lsum[20][N]; int tree[20][N],a[N],t_l[20][N]; void build(int l,int r,int id) {if(l==r) return ;int mid=(l+r)/2;int same=mid-l+1;for(int i=l;i<=r;i++) if(tree[id][i]<a[mid]) same--;int lp=l,rp=mid+1; for(int i=l;i<=r;i++){if(tree[id][i]<a[mid]){tree[id+1][lp++]=tree[id][i];lsum[id][i]=lsum[id][i-1]+tree[id][i];}else if(tree[id][i]==a[mid]&&same>0){tree[id+1][lp++]=tree[id][i],same--;lsum[id][i]=lsum[id][i-1]+tree[id][i];}else{tree[id+1][rp++]=tree[id][i];lsum[id][i]=lsum[id][i-1];}t_l[id][i]=t_l[id][l-1]+lp-l;}build(l,mid,id+1);build(mid+1,r,id+1); } ll isum; int num; int find(int l,int r,int k,int L,int R,int id) {if(l==r) return tree[id][l];int mid=(L+R)/2;int cnt=t_l[id][r]-t_l[id][l-1];if(cnt>=k){int newl=L+t_l[id][l-1]-t_l[id][L-1];int newr=newl+cnt-1;return find(newl,newr,k,L,mid,id+1);}else{num+=cnt;isum+=lsum[id][r]-lsum[id][l-1];int newr=r+t_l[id][R]-t_l[id][r];int newl=newr-(r-l-cnt);return find(newl,newr,k-cnt,mid+1,R,id+1);} } int main() {int t,n,m;scanf("%d",&t);int t1=t;while(t--){scanf("%d",&n);memset(sum,0,sizeof(sum));for(int i=0; i<20; i++) tree[i][0]=t_l[i][0]=lsum[i][0]=0;for(int i=1;i<=n;i++){scanf("%d",&tree[0][i]);a[i]=tree[0][i];sum[i]=sum[i-1]+a[i];}sort(a+1,a+n+1);build(1,n,0);scanf("%d",&m);printf("Case #%d:\n",t1-t);while(m--){int l,r;scanf("%d%d",&l,&r);if(l==r) puts("0");else{l++,r++;int k=(r-l)/2+1;num=0;//得到小于中間這個數的個數isum=0;//得到小于中間這個數的和ll x=find(l,r,k,1,n,0);printf("%I64d\n",(ll)x*(num-(r-l+1-num))+sum[r]-sum[l-1]-isum-isum);}}puts("");}return 0; } 注意 long long 。

轉載于:https://www.cnblogs.com/nyist-TC-LYQ/p/7208109.html

總結

以上是生活随笔為你收集整理的HDU-3743 Minimum Sum,划分树模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。