我说下O(NlogN)的做法.

先按照b[i]排序

考虑b[I]=k[I]*m+r[I] , 其中0<=r[I]<m

答案 $\sum_{i=1}^{n}\sum_{j=i+1}^n [{\frac{b_j - b_i}{m}}] =\sum_{i=1}^{n}\sum_{j=i+1}^n( (k_j-k_i)+[\frac{r_j-r_i}{m}])$

其中对于固定的i, $\sum_{j=i+1}^{n}{k_j}$ 可以利用后缀和计算; $\sum_{ i=j+1}^{n} (-k_i)= -(n-i)*k_i$

因此关键在于求 $\sum_{i=1}^{n}\sum_{j=i+1}^n[\frac{r_j-r_i}{m}]$

事实上，对于每对

，我们考虑:如果

,那么 $[\frac{r_j-r_i}{m}]=0$ ;否则 $[\frac{r_j-r_i}{m}]=-1$ .

因此还是对于固定的i，我们需要计算有多少个j,满足:j>i 且

。这一步可以用离散化+树状数组解决。

最后的时间复杂度是O(NlogN+N*(1+1+logN))=O(NlogN)

创作者周榜