题目大意

 

给你 n(1<=n<=10^5) 个数，分别是x(0), x(1), x(2), ..., x(n-1)。再给你 Q(1<=Q<=10^5) 个 query。

每个 query 要求对于编号在区间 [L, R] 中的所有数，找出一个 x，使得 segma{ abs( x(i)-x ) } (L<=i<=R)最小，输出这个最小的值

 

做法分析

 

首先可以肯定的是，对于一个给定的 query 区间 [st, en]，我们需要找到的 x 肯定是 x(st), x(st+1), ..., x(en) 的中位数

找到中位数之后，接下来就是求解所有的距离和了

 

找中位数可以用 划分树 log(n) 的做。但是怎么求所有的距离和呢？

我们可以在找中位数的过程中，递归的求解这个和，而这也就是本题的难点！

 

比如当前树中的区间是 [L, R] ，而我们查找的区间是 [st, en]，找的是其中的第 k 个（L<=st<=en<=R）。

假设已经找到了第 k 个是多大了，设为 keyVal

        假设 keyVal 位于当前树节点的左儿子中，我们需要将所有在 [st, en] 中的，分配在了右儿子中的数全部减去 keyVal，再加到我们的 ans 中。

        如果 keyVal 位与当期树节点的右儿子中，我们需要用 keyVal 减去每个在 [st, en] 中的，分配在了左儿子中的数，再加到我们的 ans 中

这里，我们不难想到用部分和来优化这个过程：

       定义 sum[deep][i] 表示第 deep 层，从 0 到 i 的所有数的和

然后在执行上面的过程即可

 

参考代码

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 const int N=100006; 9 typedef long long LL;10 11 struct devided_tree12 {13     int val[20][N], sorted[N], f[20][N];14     LL sum[20][N], ans;15 16     void build(int L, int R, int deep)17     {18         int mid=(L+R)>>1;19         int midVal=sorted[mid], tot=mid-L+1;20         for(int i=L; i<=R; i++)21         {22             if(val[deep][i]
          
           >1;45         int L1=(L==st)?0:f[deep][st-1];46         int L2=f[deep][en]-L1;47         int R1=(st-L)-L1;48         int R2=(en-st+1)-L2;49         if(k<=L2)50         {51             int keyVal=query(L, mid, L+L1, L+L1+L2-1, k, deep+1);52             if(R2>0)53             {54                 if(R1==0) ans=ans-keyVal*(LL)R2+sum[deep+1][mid+R1+R2];55                 else ans=ans-sum[deep+1][mid+R1]-keyVal*(LL)R2+sum[deep+1][mid+R1+R2];56             }57             return keyVal;58         }59         else60         {61             int keyVal=query(mid+1, R, mid+1+R1, mid+1+R1+R2-1, k-L2, deep+1);62             if(L2>0)63             {64                 if(L1==0) ans=ans-sum[deep+1][L+L1+L2-1]+keyVal*(LL)L2;65                 else ans=ans-sum[deep+1][L+L1+L2-1]+sum[deep+1][L+L1-1]+keyVal*(LL)L2;66             }67             return keyVal;68         }69     }70 } tree;71 72 int main()73 {74     int n, m, t;75     scanf("%d", &t);76     for(int ca=1; ca<=t; ca++)77     {78         printf("Case #%d:\n", ca);79         scanf("%d", &n);80         for(int i=0; i
          
         
        
       
      

 

AC通道