Case #1:64Case #2:00
我感觉划分树在遍历的时候最痛苦。哎，总是在推区间，，区间真的很容易推错。
有一个数列 x1..xn,要求一个数x使得 ∑(abs(xi-x))值最小，很明显，对数列进行排序后最中间的那个数就是x，可用划分树求得，那么如何求和呢，经过计算可知，既然
x 是最中间的那个数，那么最后的和 即为 x左边 xmid-x1+xmid-x2..+x(mid+1) – xmid + x(mid+2)-xmid.. 整理得 xmid*(lefnum-rignum)+rigsum-lefsum
lefnum为划分过程进入左子树的个数，lefsum为进入左子树的数之和
上面是正常的思路，我来说一个非常规的思路，int ans = 0 ；我们直接遍历的时候，如果中位数为x，如果x在左子树，那我们ans+=区间内进入右子树所有数之和。如果x在右子树，那我们ans-=区间内进入左子树的，一直到找到x结束。这样我们就巧妙的上面的俩个过程合在了一起
哎，由于错把循环变量j写成了i，，拿着别人的代码调试了一晚上，结果代码和别人的长的差不多了，，无力
另外需要注意的是，，这道题对内存要求的比较紧，，数组不能太大。
下面是代码：
#include <cstdio>#include <cstring>#include <algorithm>#define MAX 100100using namespace std ;long long sum[25][MAX];int sorted[MAX] , tree[25][MAX] ,toLeft[25][MAX] ;void creat(int L , int R , int deep){if(L == R){sum[deep][L]=tree[deep][L] ;return ;}int mid = (L+R)>>1 , same = mid-L+1;for(int i = L ; i <= R ; ++i){if(tree[deep][i]<sorted[mid])–same ;sum[deep][i] = tree[deep][i] ;if(i>L)sum[deep][i] += sum[deep][i-1] ;}int ls = L ,rs = mid+1;for(int i = L ; i <= R ; ++i){int flag = 0 ;long long num = 0;if(tree[deep][i]<sorted[mid] || (tree[deep][i]==sorted[mid] && same)){tree[deep+1][ls++]=tree[deep][i] ;if(tree[deep][i] == sorted[mid])–same ;flag = 1 ;}else{tree[deep+1][rs++] = tree[deep][i] ; }toLeft[deep][i] = toLeft[deep][i-1]+flag ;}creat(L,mid,deep+1) ;creat(mid+1,R,deep+1) ;}long long ans = 0;int query(int L , int R , int x , int y , int k , int deep){if(x == y){return tree[deep][x] ;}int mid = (L+R)>>1;int lxl = toLeft[deep][x-1] – toLeft[deep][L-1] ;int lyl = toLeft[deep][y] – toLeft[deep][L-1] ;int xyl = toLeft[deep][y] – toLeft[deep][x-1] ;int lxr = x-L-lxl ;int lyr = y-L+1-(toLeft[deep][y]-toLeft[deep][L-1]) ;if(k<=xyl){if(lyr>0){if(lxr>0){ans += sum[deep+1][mid+lyr]-sum[deep+1][mid+lxr];}else{ans += sum[deep+1][mid+lyr] ;}}return query(L,mid,L+lxl,L+lyl-1,k,deep+1);}else{if(lyl>0){if(lxl>0)ans-=sum[deep+1][L+lyl-1]-sum[deep+1][L+lxl-1];elseans -= sum[deep+1][L+lyl-1] ;}return query(mid+1,R,mid+lxr+1,mid+lyr,k-xyl,deep+1);}}int main(){int t ;scanf("%d",&t);for(int i = 1 ; i <= t ; ++i){int n ;scanf("%d",&n);memset(toLeft,0,sizeof(toLeft)) ;for(int j = 1 ; j <= n ; ++j){scanf("%d",&sorted[j]) ;tree[0][j] = sorted[j] ;}sort(sorted+1 , sorted+n+1) ;creat(1,n,0) ;int r ;printf("Case #%d:\n",i) ;scanf("%d",&r) ;for(int j = 0 ; j < r ; ++j){int l,ri;scanf("%d%d",&l,&ri) ;++l,++ri;int k = (ri-l)/2+1;ans = 0 ;int d = query(1,n,l,ri,k,0);if((ri-l+1)%2 == 0){ans -= d ;}printf("%I64d\n",ans);}printf("\n") ;}return 0 ;}
每个人心中，都会有一个古镇情怀，流水江南，烟笼人家。
