题解：P11794 [JOI 2016 Final] 集邮比赛 2 / Collecting Stamps 2

· · 题解

首先，要放 J 就放开头，要放 I 就放末尾就会最优。
这可由子序列的定义直接推出。

对于 O 而言，如果它放下标为 i - 1 和 i 的字母之间，其贡献是 i - 1 及以前的 J 的数量乘 i 及以后的 I 的数量。其中 1 \le i \le n + 1。
因为这个 O 加进来后，原来的数量不变，直接加上其贡献即可。

所以只需给 J 的数量做前缀和，I 的数量做后缀和即可。