自动搬运

查看原文

来自洛谷，原作者为

	x_angelkawaii_x **

搬运于2025-08-24 22:21:37，当前版本为作者最后更新于2020-05-05 14:54:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• 子任务 $1,2$

按照题意模拟，构建出数表。查询时暴力枚举。
复杂度 $\mathcal{O}(n^3+qn^2)$ ，期望得分 $10$ 分。

• 子任务 $3$

记 $(i,j)$ 位置处的数字为 $f_{ij}$

则

$$f_{ij}=\lfloor \frac{\sum_{x=min(i,j)}^{max(i,j)}a_x}{k} \rfloor $$

所以 $\mathcal{O}(n^2)$ 构造数表，查询时利用二维前缀和即可。

时间复杂度为 $\mathcal{O}(n^2+q)$，期望得分 $20$ 分。

过渡：

对于之后的子任务，$n$ 非常大，所以我们很难还原出整个数表。

为了方便起见我们不妨将问题转化到数列上：

记 $a_i$ 前缀和为 $s_i$，对于询问 $l_1,r_1,l_2,r_2$，答案为

$$\sum_{l_1\le i \le r_1}\sum_{l_2 \le j \le r_2}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor $$

根据 $[l_1,r_1]$，$[l_2,r_2]$ 两个区间的位置关系(相离，相交，包含)，我们有不同的容斥策略将所求化为若干个 $\sum_{l\le i \le r}\sum_{l \le j \le r}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor$ 的形式，此处留给读者自行思考。

所以经过一番转化，我们的问题转化成了如下形式，即求解

$$\sum_{l\le i \le r}\sum_{l \le j \le r}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor $$

• 子任务 $5$

$k=1$，要求求解

$$\sum_{l\le i \le r}\sum_{l \le j \le r}( s_j-s_{i-1} ) $$

简单算一下每个 $s$ 的出现次数即可。

复杂度 $O(q)$ ，期望得分 $35$分。

• 子任务 $6$

$k=2$，每次询问求解的式子为 $\sum_{i=l}^{r}\sum_{j=i}^{r}\lfloor \frac{s_j-s_{i-1}}{2} \rfloor$，可以很自然地想到分类讨论 $s_j$ 和 $s_{i-1}$ 同奇，同偶或一奇一偶三种情况

考虑另 $c_i= \lfloor \frac{s_i}{2} \rfloor,d_i=s_i\bmod 2$，则 $s_i=2c_i+d_i$，此时 $\lfloor \frac{s_j-s_{i}}{2} \rfloor=(c_j-c_i)-[d_j<d_i]$

发现作差的两个 $s$ 是错位的，所以我们进行简单地容斥：

$$\sum_{i=l}^{r}\sum_{j=i}^{r}\lfloor \frac{s_j-s_{i-1}}{2} \rfloor=\sum_{i=l}^{r-1}\sum_{j=i+1}^{r-1}\lfloor \frac{s_j-s_i}{2} \rfloor+\sum_{j=l}^{r}\lfloor \frac{s_j-s_{l-1}}{2}\rfloor+\sum_{i=l}^{r}\lfloor \frac{s_r-s_{i-1}}{2}\rfloor-\lfloor \frac{s_r-s_{l-1}}{2}\rfloor $$

记 $p_i=\sum_{j=1}^{i}c_j$，$P_i=\sum_{j=1}^{i}p_j$，$C_i=\sum_{j=1}^{i}j*c_j$

$$\sum_{j=l}^{r}\lfloor \frac{s_j-s_{l-1}}{2}\rfloor=\sum_{j=l}^{r}((c_j-c_{l-2})-[d_j<d_{l-1}])=p_r-p_{l-1}-(r-l+1)c_{l-1}-\sum_{j=l}^{r}[d_j<d_{l-1}] $$

由于 $d_i$ 只有 $01$ 两种取值，因此开一个记录 $1$ 位置的树状数组通过差分即可求出$\sum_{j=l}^{r}[d_j<d_{l-1}]$

$\sum_{i=l}^{r}\lfloor \frac{s_r-s_{i-1}}{2}\rfloor$ 求解方式类似，不做展开

$$\sum_{i=l}^{r}\sum_{j=i+1}^{r}\lfloor \frac{s_j-s_i}{2} \rfloor=\sum_{i=l}^{r}\sum_{j=i+1}^{r}((c_j-c_i)-[d_j<d_i])=\sum_{i=l}^{r}\sum_{j=i+1}^{r}(c_j-c_i)-\sum_{i=l}^{r}\sum_{j=i+1}^{r}[d_j<d_i] $$

左式 $=\sum_{i=l}^{r}(\sum_{j=i+1}^{r}c_j-(r-i)c_i)=\sum_{i=l}^{r}(p_r-p_i-r*c_i+i*c_i)=(r-l+1)p_r-(P_r-P_{l-1})-r(p_r-p_{l-1})+C_r-C_{l-1}$

由于 $d_i$ 只有 $01$ 两种取值，因此使用线段树维护区间 $0,1$ 的个数和逆序对个数即可求出右式

复杂度 $\mathcal{O}(n\log n)$，期望得分 $50$ 分

• 子任务 $4$

$q=1$ 且询问区间为 $[1,n]$

仿照子任务6，求出 $c_i= \lfloor \frac{s_i}{k} \rfloor,d_i=s_i\bmod k$，化简步骤相同

$\sum_{j=l}^{r}[d_j<d_{l-1}]$ 即全局逆序对

与子任务 $4$ 算法结合，期望得分 $70$ 分

• 子任务 $5$

在 $6,4$ 的基础上，算法的瓶颈是需要求出 $\sum_{i=l}^{r}\sum_{j=i+1}^{r}[d_j<d_i]$，即区间逆序对个数

由于询问不强制在线，可以使用二次离线莫队 $\mathcal{O}(n\sqrt{n})$ 求解

其次就是 $\sum_{j=l}^{r}[d_j<d_{l-1}]$ 的求解，这个可以将 $d_i$ 和询问排序后用双指针+树状数组的方法 $\mathcal{O}(n\log n)$ 求解

时间复杂度 $\mathcal{O}(n\sqrt{n}+n\log n)$，空间复杂度 $\mathcal{O}(n)$，可以通过此题