题解：CF2069C Beautiful Sequence
arrow_king
·
·
题解
观察性质发现，合法的序列只有可能是 1,2,2,\dots,2,3，其中至少有一个 2。
一个朴素的想法是枚举所有的 1 和所有的 3，记它们之间 2 的数量是 c，则他们的贡献是 2^c-1。但是这样的时间复杂度是 O(n^2)，无法通过。
考虑对每个 1 求出其后面所有 3 的总贡献。记 s_i 表示 i 位置之前 2 的数量，那么 i\sim j 之间的贡献是 2^{s_j-s_{i-1}}-1。再设 p_i 表示 i 后面 3 的数量。考虑一个位置 i 的贡献：
\begin{aligned}
\sum_{j>i,a_j=3}(2^{s_j-s_{i-1}}-1)&=\sum_{j>i,a_j=3}2^{s_j-s_{i-1}}-p_i\\
&=\dfrac{1}{2^{s_{i-1}}}\sum_{j>i,a_j=3}2^{s_j}-p_i
\end{aligned}
只需要维护 [a_i=3]2^{s_i} 的后缀和即可，复杂度 O(n\log\mathrm{mod})。