本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 10:51:44

记录

AB 切，C 想很久以后吃一发切，D 想一小会后吃一发切，E 最后开始搞线段树，最后发现假了，其实不难。

题解

A. Alice and Books

显然不管怎么分，$A_n$ 一定会贡献到答案中，因此只需要从其余元素中找到最大的单独分一组即可，答案为 $A_n+\max_{i=1}^{n-1}A_i$

B. New Bakery

推式子，当取 $k$ 时，结果为 $(n-k)a+\sum_{i=b-k+1}^bi$，等差数列求和并合并同类项，整理为 ${res}=-\frac12k^2+(b-a +\frac12)k+an$，是 ${res}$ 关于 $k$ 的二次函数，当 $k=b-a+\frac12$ 时取到最大值。由于 $k$ 为整数，同时值域为 $[0,min(n,b)]$，取最接近对称轴的整数即可。

C. Manhattan Permutations

由于 $p$ 是一个排列，如果由 $i$ 向 $p_i$ 连边，每个点的出度和入度都为 $1$，得到的一定为若干个环。考虑构造使得每个环中只有一个 $i$ 满足 $p_i\le i$，因为如果有两个这样的 $i$，直接将其中一个拆出来答案不变，所以这样一定包含了所有方案。

考虑每个环对曼哈顿值的贡献，由于只有一个 $p_i\le i$ 的 $i$，所以整个环的贡献就是 $2(\max(i)-min(i))$，因此最终值也一定是偶数。所以这里把 $k$ 直接除掉了 $2$，只考虑一边的贡献。

之后考虑最大化曼哈顿值，发现将 $i$ 与 $n-i+1$ 两两组合，组成 $\lfloor\frac n2\rfloor$ 个二元环，最终值最大，等差数列求和得到最大值为 $(n+n\mod 2)\lfloor\frac n2\rfloor$，之后贪心地从大到小交换即可。

只有一种特殊情况是在 $n$ 为奇数时，有可能最后剩下 $k=1$ 而没有距离为 $1$ 的点对，这时暴力找到一个没有改变位置的 $i$，将其与 $i+1$ 交换即可，此时若 $i+1$ 未被交换则这两个点贡献 $1$，否则变成三元环，总贡献也会增加 $1$

D. Elections

可以把 $c$ 直接加给 $a_1$，显然跟原题意是等价的。之后求出 $a$ 中最靠前的最大值编号 $k$，显然 $k$ 的答案为 $0$。

考虑其他 $x$ 的答案。由于 $a_x$ 本身已经不是最大值，并且即使是去掉目前最大的 $a_k$，这一部分也会加到编号最小的 $a_i$ 上，最大值一定不降。所以至少要将 $x$ 之前的 $x-1$ 个人全部去掉，才能使 $x$ 为编号最小，$a_x$ 增加以变为最大。

所以维护 $a$ 的前缀和 $s$，若 $s_x\ge a_k$，只需要把前面全去掉即可，答案为 $x-1$。否则需要把前面全去掉，并且把 $x$ 后面的最大值 $a_k$ 也去掉，答案为 $x$。

E. Computing Machine

考虑一个区间的最优操作方案，发现先用 $s$ 中的 $0$ 把 $t$ 中所有能变 $1$ 的变完，再把 $s$ 中所有能变 $1$ 的变完，这样一定是最优的，因为这样保证了第一步之后 $t$ 中的 $1$ 最多，从而最终 $s$ 中的 $1$ 也最多。

接着考虑每一位会怎样被改变。若 $s_i$ 被变为 $1$，需要 $t_{i-1}=1$ 且 $t_{i+1}=1$，$t$ 的这两位又会受到 $s_{i-2},s_i,s_{i+2}$ 的影响，所以对于每一位 $s_i$，都只会受到 $[i-2,i+2]$ 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 $s$ 求前缀和。询问长度不超过 $4$ 时直接暴力操作求解。超过 $4$ 时由于 $[l+2,r-2]$ 只受区间 $[l,r]$ 内的影响，答案不变，直接记录下原来的答案，再单独对 $[l,l+4]$ 操作并记录前两位的答案，对 $[r-4,r]$ 操作并记录后两位的答案，把三部分相加即可。