给定长为 \(n\) 的数列 \(a\)，你需要构造一个长为 \(2n\) 的数列 \(b\)，且 \(a_i=b_{2i-1}+b_{2i}\)，\(b_i>0\)，最小化将 \(b\) 的相同数字缩到一起后 \(b\) 的长度。\(n\leqslant 10^5\)，\(2\leqslant a_i\leqslant 10^9\)。
我们发现可以一开始让答案为 \(2n\)，然后每有两个相邻的相同的数就让答案 \(-1\)，故我们只需要最大化相邻的相同的数的数目。
先考虑暴力 dp，设 \(f(i,j)\) 为考虑了前 \(i\) 个数，且 \(d_i=j\) 时最多有多少相邻的相同的数。设 \(a_i=x\)，我们有三类转移： \[ f(i,j)=\max_{k=1}^{a_{i-1}-1} f(i-1,k)+[x-j=k]+[2j=x] \] 我们注意到，\(\max f(i-1,k)\) 可以向任何位置转移，所以对于相同的 \(i\)，\(\max f(i,k)-\min f(i,k)\leqslant 2\)。
接下来，我们把第一维砍掉，设 \(i-1\) 的 dp 数组为 \(g\)，\(maxg\) 为其最大值，\(i\) 的为 \(f\)，那么我们可以把转移看成三步：
- 令所有 \(f(i)=maxg\)。
- 对所有 \(\max(1,x-a_{i-1}+1)\leqslant i <x\)，\(f(i)=\max(f(i),g(x-i)+1)\)。
- 若 \(2i=x\)，\(f(i)=f(i)+1\)。
现在，我们令变量 \(zero\) 表示同一层（\(i\) 相同）中最小的 \(f\) 的值，集合 \(one\) 表示 \(f(i)=zero+1\) 的所有下标 \(i\)，\(two\) 表示是否存在 \(f(i)=zero+2\) 的 \(i\)，有记录其下标，反之为 \(-1\)。不难发现 \(two\) 一定等于 \(-1\) 或 \(\dfrac{x}{2}\)。
现在，我们考虑怎么维护新考虑一个元素的影响后 \(zero,one,two\) 的变化，我们对是否存在 \(f(i)=zero+2\) 和 \(f(i)=zero+1\) 的情况分类讨论，我们先考虑上面的前两步转移，最后一步可以一起进行：
- 当 \(two\not= -1\) 时，所有数都由 \(two\) 转移过来一定不劣，把 \(one\) 清空，然后 \(zero:=zero+2\)，然后考虑新的 \(one\)，其只可能包含元素 \(x-two\)。
- 当 \(two=-1\) 但 \(one\) 不为空时，先让所有数从 \(one\) 中转移过来，故 \(zero:=zero+1\)，然后考虑枚举所有 \(one\) 中所有的数 \(t\)，如果 \(x-t>0\)，则 \(x-t\) 在新的 \(one\) 中，将 \(t\) 变为 \(x-t\)，反之将 \(t\) 删除。
- 当 \(two=-1\) 且 \(one=\emptyset\) 时，\(zero\) 不变（真的一定不变吗？），然后我们把 \(1\sim \min(x,a_{i-1})-1\) 插入到 \(one\) 中。
然后是最后一步，如果 \(2\mid x\) 且 \(\dfrac{x}{2}\) 在 \(one\) 中，就把其从 \(one\) 中删掉，然后令 \(two=\dfrac{x}{2}\)，反之 \(two=-1\)。
我们注意到，我们一次对 \(one\) 的操作有只可能有以下几种：插入一条线段；删除一些线段；断开最多两条线段；把所有线段关于某一个点对称。注意到多次对称操作是可以合并的，我们只需要维护两个变量 \(shifter\) 和 \(sign\) 表示所有在 \(one\) 中显示的元素 \(x\) 实际上为 \(shifter+sign\cdot x\)，这样反转只需要让 \(sign\) 乘上 \(-1\)，也能计算出新的 \(shifter\)。由于每一次最多让线段的条数变多 \(2\)，每条线段最多被插入一次，这样我们可以用 std::set 维护线段，总复杂度为 \(O(n\log n)\)。
刚才提到 \(two=-1\) 且 \(one=\emptyset\) 的情况，可能有 \(x=a_{i-1}\)，这时所有元素都被插入到 \(one\) 中了，\(zero\) 应该 \(+1\)，但是这时一定不会有 \(maxf=zero+3\)，所以不加对后面的转移也不造成影响，没有必要特判。
代码：
1 |
|