给定一个长度为 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 的情况下，序列中负数数量的奇偶性不会发生变化。