题意：
给你一个双端队列，同时有一个长度为 \(n\) 的序列 \(a\)，满足序列中的元素均为 \(2\) 的非负整数幂。
从前到后遍历这个序列，对于一个 \(a_i\) 你可以将它放入双端队列的队首或是队尾。如果队列中出现两个相邻元素值相同，那么它们就会被合并成它们的和。
问最后是否存在方案使得队列最后只剩一个元素。存在输出方案。
数据范围：\(n \le 1000,\sum{a_i} \le 2^{13}\)。
思路：
考虑到双端队列中如果存在三个相邻元素 \(a,b,c\) 满足 \(a>b<c\)，那么 \(a\) 和 \(c\) 最终一定无法合并。
所以合法方案中的双端队列的元素一定单峰的。
我们把它以峰的位置劈成两半，然后每一半就都是单调的，可以直接用一个长度不超过 \(2^{13}\) 次方的数来表示。
令 \(f(i,j,k)\) 表示当前 \(1 \sim i\) 的元素入队，队列一半是 \(j\)，一半是 \(k\)。
转移就直接枚举 \(a_{i+1}\) 放左边还是右边就行了，可以用 \(\operatorname{lowbit}\) 快速得到队首和队尾的值，加入直接 \(j \gets j+a_{i+1}\) 或 \(k \gets k + a_{i+1}\) 即可。
注意峰值改变要特殊处理。
最后发现 \(j+k=\sum_{p=1}^{i} a_p\)，所以可以直接省掉一维。
时间复杂度 \(\Theta(n \sum{a_i})\)。
标签：队列,双端,sum,元素,队首,序列,Luogu7093 From： https://www.cnblogs.com/zzzYheng/p/16916031.html