自动搬运

查看原文

来自洛谷，原作者为

	Albert_Wei 听取 WA 声一片

搬运于2025-08-24 22:53:47，当前版本为作者最后更新于2023-12-27 20:09:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

我们考虑转化一下询问。设 $pre_i = \sum \limits_ {j = 1} ^ {i - 1} [a_j \neq a_{j + 1}]$，$[l,r]$ 中共有 $cnt_{l,r,x}$ 个 $x$ 从左到右分别位于 $pos_1, pos_2, \cdots , pos_{cnt_{l, r, x}}$ 则询问的答案为 $\sum \limits_ {i = 1} ^ {cnt_{l, r, x}} \sum \limits_ {j = i + 1} ^ {cnt_{l, r, x}} (pre_{pos_j} - pre_{pos_i}) = \sum \limits_ {i = 1} ^ {cnt_{l, r, x}} (2 \times i - cnt_{l, r, x} - 1) \times pre_{pos_i}$ $^{[1]}$。然后我们就会 $\mathcal{O}(n^2)$ 了。

考虑序列分块，块长 $\sqrt n$，每块的左有端点为 $L_i, R_i$ 每个位置所属的块为 $bel_i$，定义 $preB_i = \sum \limits_ {j = L_{bel_i} - 1} ^ {i - 1} [a_j \neq a_{j + 1}]$。 对于每块维护这样的东西：

$$cnt_{i,j} = \sum \limits_ {k = L_i} ^ {R_i} [a_k = j] $$$$sum_{i,j} = \sum \limits_ {k = L_i} ^ {R_i} [a_k = j] \times preB_k $$$$ans_{i,j} = 2 \sum \limits_ {k = L_i} ^ {R_i} [a_k = j] \times preB_k \times (\sum \limits_ {x = L_i } ^ {k - 1} [a_x=j]) $$

$\mathcal{O}(\sqrt n)$ 重构一个块是简单的。

修改：散块直接暴力重构，整块相当于把 $preB,sum$ 和 $ans$ 清空，然后 $cnt_{i,x} = R_i - L_i + 1$ 其他清空，打个标记就行了。

查询：散块直接暴力，整块先前缀和一下，算出 $pre_{L_i - 1}$，然后就有

$$Bsum = sum_{i,x} + pre_{L_i - 1} \times cnt_{i,x} = \sum \limits_ {k = L_i} ^ {R_i} [a_k = j] \times pre_k $$$$Bans = ans_{i,x} + pre_{L_i - 1} \times cnt_{i,x} \times (cnt_{i,x} - 1) = 2 \sum \limits_ {k = L_i} ^ {R_i} [a_k = j] \times pre_k \times (\sum \limits_ {x = L_i} ^ {k - 1} [a_x=j]) $$

由于系数是一个公差为 $2$ 的等差数列，根据上面的公式 $[1]$ 算一算首项就可以通过 $Bcnt,Bans$ 算出答案了。我不太确定这么搞会不会爆 ll，不过用 ull 就行了。

然后我们就会 $\mathcal{O}(n \sqrt n)$ 时空的低能做法了，但是 lxl 把空间限制调成了 $64MB$ 然后这种做法就寄了。但是我们可以直接把询问离线，然后逐块处理，这样似乎就可以 $\mathcal{O}(n)$ 空间，然后似乎就能过题了。感觉细节可能比较多，代码先咕咕咕。