Round825 Div2 E

题目描述

给定一个序列，每次可以选择相邻两个数进行交换，并将其中之一赋值为0，或者不交换。操作之后将的值提交给答案。问答案最大值是多少。

解题思路

考虑每个数的答案可以从哪里贡献，只有和两种。

当时，答案一定是从贡献而来；

当时，答案可能从左侧也可能从右侧贡献而来。

记表示处理到位置，交换次，最后一次贡献位置为的答案贡献。

从左侧贡献答案时，

从右侧贡献答案时，

注意到max只有第3维与有关，可以使用前缀和优化来做。

考虑边界条件，主要是限制和。，。

注：当使用前缀和优化时，有的答案是不合法的，但它的前缀中有合法的答案，这些答案也应该被计算，以提供给后面的值使用。