自动搬运

查看原文

来自洛谷，原作者为

	dongzirui0817 这个人不懒，但还是什么也没留下

搬运于2025-08-24 23:10:17，当前版本为作者最后更新于2025-07-06 13:42:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

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