P9998 做题记录

· · 题解

我们考虑转化一下询问。设 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]) 修改：散块直接暴力重构，整块相当于把 $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)$ 空间，然后似乎就能过题了。感觉细节可能比较多，代码先咕咕咕。