使用造计算机思想解决问题（构造操作）

或许可以看作是一类可以迁移运用的构造（？）题套路？

核心思想就是多次加强 / 削弱 / 扩展题目中给出的操作，得到性质更好 / 更容易利用 / 更简洁的新操作，通过新操作解决整个问题。

Example 1

给定一个长度为 $n$ 的整数数组 $a$ 和一个包含 $m$ 个正整数的集合 $B$ ，其中 $1 \leq b_i \leq \color{red}{\lfloor \frac{n}{2} \rfloor},1\le i\le m$ 。

你可以对 $a$ 进行如下操作：选择某个 $x$ ，其中 $x$ 必须出现在 $B$ 中。然后在集合 $B$ 中选择从数组 $a$ 中选择一个长度为 $x$ 的区间，将该区间内的每个元素都乘以 $-1$ 。

问执行若干次上面给出的操作后，数组 $a$ 所有元素之和 $\sum\limits_{i=1}^n {a_i}$ 的最大值。

Data Range: $2\le n\le 10^6,1\le m\le \color{red}{\lfloor\frac n2\rfloor}$

Solution 1

题目给了 $m$ 个不同长度的区间取反操作，考虑使用原有的这些操作构造出更通用而且性质更优美的新操作。注意到记 $g=\gcd(b_1,b_2,\ldots,b_m)$ ，则必然存在一组整数 $c_1,c_2,\ldots,c_m$ 满足 $g=\sum\limits_{i=1}^mc_ib_i$ ，因此可以构造出这样的一个操作：每次取反序列中连续的 $g$ 个数。记这个操作为操作 $1$ 。

发现这个操作仍然没有太好的性质，因此考虑继续构造新操作：注意到若第一次操作反转了区间 $[l,l+g-1]$ 内的数，第二次操作反转了区间 $[l+1,l+g]$ 内的数，则两次操作结束后只有位置 $l,l+g$ 的数被反转。因此又可以构造出一个新的操作：每次在序列中选择两个距离恰好为 $g$ 的数，并将这两个数反转。记这个操作为操作 $2$ 。

但是构造出的操作 $2$ 不和操作 $1$ 一样和原有操作形成充要条件，这个新构造出的操作过于强，也就是说该操作的必要性是不成立的，这里我们先假装操作 $2$ 同样形成了充要条件解决该问题：注意到若将序列按照下标 $\bmod\ g$ 的结果分为 $g$ 个不同的序列，则不同序列之间互相独立。对于单个序列而言可以看作是每次将相邻两个位置的值取反，执行若干次操作后让单个序列内所有元素的和最大。考虑寻找执行操作后得到的不变量，注意到此时不论怎么对序列执行操作，在不考虑 $0$ 的情况下，序列中负数数量的奇偶性不会发生变化。

对单个序列而言这个操作的性质还是不够强，因此考虑对于单个独立序列的两个不同位置 $i,j$ （ $i<j$ ），依次对 $i,i+1$ ， $i+1,i+2$ ， $\ldots$ ， $j-1,j$ 这些位置分别执行操作，则最终只有 $i,j$ 两个位置的符号会发生变化。因此又构造出了新的操作 $3$ ：对一个新的序列而言，每次可以任意选择两个不同的位置，并将两个位置的值都取反。容易证明操作 $3$ 和操作 $2$ 互为充要条件。